ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214982 | #2037. a | KXG | 100 | 4983ms | 95252kb | C++11 | 1.6kb | 2024-11-25 19:11:54 | 2024-11-25 23:01:33 |
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node {
long long l, r, ans;
node() : l(0), r(0), ans(0) {}
node(char s) : l(s == ')'), r(s == '('), ans(0) {}
node(long long l, long long r, long long ans) : l(l), r(r), ans(ans) {}
};
node merge(node a, node b) {
long long newans = min(a.r, b.l);
return node(a.l + b.l - newans, a.r + b.r - newans, a.ans + b.ans + 2 * newans);
}
struct segmenttree {
char s[1000010];
node val[4000010];
void pushup(int p) {
val[p] = merge(val[p << 1], val[p << 1 | 1]);
}
void build(int p, int l, int r) {
if (l == r) {
val[p] = node(s[l]);
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
// printf("%d %d %d : %lld %lld %lld\n", p, l, r, val[p].l, val[p].r, val[p].ans);
}
node query(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return val[p];
}
node ans;
int mid = (l + r) >> 1;
if (L <= mid) {
ans = merge(ans, query(p << 1, l, mid, L, R));
}
if (R > mid) {
ans = merge(ans, query(p << 1 | 1, mid + 1, r, L, R));
}
return ans;
}
} sgt;
int n, q, l, r;
int main() {
scanf("%s", sgt.s + 1);
scanf("%d", &q);
n = strlen(sgt.s + 1);
sgt.build(1, 1, n);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &l, &r);
printf("%lld\n", sgt.query(1, 1, n, l, r).ans);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 15ms
memory: 94276kb
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: 7ms
memory: 94280kb
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: 20ms
memory: 94276kb
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: 16ms
memory: 94280kb
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: 8ms
memory: 94276kb
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: 19ms
memory: 94280kb
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: 1182ms
memory: 95252kb
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: 1215ms
memory: 95248kb
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: 1237ms
memory: 95248kb
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: 1264ms
memory: 95248kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
result:
ok 1000000 lines