ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214981 | #2037. a | ThySecret | 100 | 4602ms | 43160kb | C++11 | 2.4kb | 2024-11-25 19:04:24 | 2024-11-25 23:01:16 |
answer
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
template<typename Type>
inline void read(Type &res)
{
res = 0;
int ch = getchar(), flag = 0;
while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }
int n, q;
char str[N];
struct SegsTree
{
#define lc u << 1
#define rc u << 1 | 1
struct Node { int l, r, sum, lft, rht; } tr[N << 2];
friend Node operator + (const Node &a, const Node &b)
{
Node res = Node{a.l, b.r, 0, 0, 0};
res.sum = a.sum + b.sum, res.lft = a.lft, res.rht = b.rht;
int rest = min(a.rht, b.lft);
res.sum += 2 * rest, res.lft += b.lft - rest, res.rht += a.rht - rest;
return res;
}
inline void pushup(int u) { tr[u] = tr[lc] + tr[rc]; }
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if (l == r)
{
if (str[l] == '(') tr[u].rht = 1;
else tr[u].lft = 1;
return;
}
int mid = l + r >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
pushup(u);
}
Node query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (l > mid) return query(rc, l, r);
else if (r <= mid) return query(lc, l, r);
else return query(lc, l, r) + query(rc, l, r);
}
} SGT;
signed main()
{
scanf("%s%d", str + 1, &q), n = strlen(str + 1);
SGT.build(1, 1, n);
// cout << SGT.query(1, 1, n).sum << '\n';
while (q --)
{
int l, r; read(l, r);
cout << SGT.query(1, l, r).sum << '\n';
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
(()))())))(())()())()()))((((()()))((((()((())()))(()((((()(())(())(()))())()())()())(())(()()((((((...
output:
854 136 108 12 836 206 550 252 536 266 220 344 830 502 170 290 522 526 464 98 160 10 840 298 332 272...
result:
ok 1000 lines
Test #2:
score: 10
Accepted
time: 1ms
memory: 1272kb
input:
)))((()())((())((()()())())(((())())((()((())(())()((((((())))((()(()())))(()()(())())()))(()()))(((...
output:
30 22 96 382 252 154 386 56 434 102 590 456 114 56 346 252 324 12 138 184 320 52 380 470 64 476 40 4...
result:
ok 1000 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 1272kb
input:
(()((())))))))((())(()()))()))()()())(()))(())))))))(((())((((((((((()((()())()(()(())(()())(()))(((...
output:
674 192 100 168 206 244 378 746 184 196 196 602 414 302 224 358 232 482 154 448 168 704 232 232 810 ...
result:
ok 1000 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
))))))))()))())()(()()())()())(((()())(((()(((()()))(()()()))())(()()(()()())()(())()())))))()((((()...
output:
168 378 240 380 548 324 54 492 724 276 184 398 66 452 404 192 192 594 192 128 918 424 516 46 108 430...
result:
ok 1000 lines
Test #5:
score: 10
Accepted
time: 1ms
memory: 1268kb
input:
((())))(()((()()))()))))((((()()()()()()()))()()(()(())(()((()))()((())))))()(((()())()))()())))(())...
output:
634 386 334 6 246 372 226 424 274 168 254 448 312 112 532 126 594 780 112 150 68 470 260 150 22 322 ...
result:
ok 1000 lines
Test #6:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
))((()))()(())())(()()))))()()((((()()())()((())(())))))(())))()())()()(())()(())())(()())))(()()))(...
output:
728 224 580 200 784 152 280 194 0 664 278 260 630 328 816 470 388 736 82 132 406 440 140 12 276 776 ...
result:
ok 1000 lines
Test #7:
score: 10
Accepted
time: 1118ms
memory: 43160kb
input:
((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...
output:
142860 235344 446706 759772 134088 748980 83870 685562 31730 572204 366368 67746 18554 603330 946486...
result:
ok 1000000 lines
Test #8:
score: 10
Accepted
time: 1183ms
memory: 43160kb
input:
())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...
output:
583148 425884 255036 448502 200322 256890 167684 114904 55236 440164 138094 879918 580038 452166 984...
result:
ok 1000000 lines
Test #9:
score: 10
Accepted
time: 1123ms
memory: 43160kb
input:
)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...
output:
47942 241400 323510 553980 111490 20570 51892 169422 82080 124416 107806 804528 123414 274334 135650...
result:
ok 1000000 lines
Test #10:
score: 10
Accepted
time: 1176ms
memory: 43160kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
result:
ok 1000000 lines