ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215025 | #2037. a | naroto2022 | 100 | 4810ms | 67668kb | C++ | 1.5kb | 2024-11-25 20:08:55 | 2024-11-25 23:08:23 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int MN=1e6+5;
ll n,q;
struct tree{
ll lsum,rsum,l,r;
void clear(){lsum=rsum=0;}
}t[MN<<2];
char ch[MN];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void update(ll p){
ll num=min(t[ls].lsum,t[rs].rsum);
t[p].lsum=t[ls].lsum+t[rs].lsum-num;
t[p].rsum=t[ls].rsum+t[rs].rsum-num;
}
void build(ll p, ll l, ll r){
t[p].l=l;t[p].r=r;
if(l==r){
if(ch[l]=='(') t[p].lsum=1;
else t[p].rsum=1;
return;
}
ll mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
update(p);
}
tree query(ll p, ll l, ll r){
if(l<=t[p].l&&t[p].r<=r) return t[p];
ll mid=(t[p].l+t[p].r)>>1;tree res;res.clear();
if(r<=mid) return query(ls,l,r);
if(l>mid) return query(rs,l,r);
tree lc=query(ls,l,r),rc=query(rs,l,r);
ll num=min(lc.lsum,rc.rsum);
res.lsum=lc.lsum+rc.lsum-num;
res.rsum=lc.rsum+rc.rsum-num;
return res;
}
int main(){
scanf("%s",ch+1);n=strlen(ch+1);
build(1,1,n);
q=read();while(q--){
ll l=read(),r=read();
tree ans=query(1,l,r);
write((r-l+1)-ans.lsum-ans.rsum);putchar('\n');
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1224kb
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: 0ms
memory: 1224kb
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: 1224kb
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: 1224kb
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: 0ms
memory: 1228kb
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: 1224kb
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: 1138ms
memory: 67668kb
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: 1242ms
memory: 67668kb
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: 1236ms
memory: 67668kb
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: 1194ms
memory: 67668kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
result:
ok 1000000 lines