ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215028 | #2037. a | Invisible_H | 100 | 5663ms | 136712kb | C++ | 1.5kb | 2024-11-25 20:18:34 | 2024-11-25 23:08:52 |
answer
#include<bits/stdc++.h>
using namespace std;
const int MX=1000010,INF=0x3f3f3f3f;
struct node{
int lc,rc,sum;
}tree[MX<<5];
int head[MX],root[MX],cnt=0;
inline void update(int now){
tree[now].sum=tree[tree[now].lc].sum+tree[tree[now].rc].sum;
}
inline int new_node(int now){
tree[++cnt]=tree[now];
return cnt;
}
inline void add_node(int now,int val){tree[now].sum=val;}
void build(int &now,int lt,int rt){
if(lt==rt) return ;
int mid=(lt+rt-1)>>1;
build(tree[now].lc,lt,mid),build(tree[now].rc,mid+1,rt);
}
void add(int &now,int lt,int rt,int pos,int val){
if(lt>pos||pos>rt) return ;
now=new_node(now);
if(lt==rt) return add_node(now,val);
int mid=(lt+rt-1)>>1;
add(tree[now].lc,lt,mid,pos,val),add(tree[now].rc,mid+1,rt,pos,val);
return update(now);
}
int cy(int now,int lt,int rt,int l,int r){
if(lt>r||rt<l) return 0;
if(l<=lt&&rt<=r) return tree[now].sum;
int mid=(lt+rt-1)>>1;
return cy(tree[now].lc,lt,mid,l,r)+cy(tree[now].rc,mid+1,rt,l,r);
}
int input[MX],n,w[MX];
stack<int>st;
signed main(){
string s;cin>>s;n=s.size();
for(int i=1;i<=n;i++) input[i]=(s[i-1]=='(');
for(int i=1;i<=n;i++){
if(input[i]) st.push(i);
else if(!st.empty()) w[i]=st.top(),st.pop();
// printf("%d ",w[i]);
}
build(root[0],1,n);
for(int i=1;i<=n;i++){
root[i]=root[i-1];
add(root[i],1,n,w[i],1);
}
int q;scanf("%d",&q);
while(q--){
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",(cy(root[r],1,n,l,n)<<1));
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1348kb
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: 1344kb
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: 1348kb
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: 1352kb
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: 1340kb
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: 1344kb
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: 1414ms
memory: 136448kb
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: 1399ms
memory: 136444kb
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: 1382ms
memory: 136444kb
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: 1468ms
memory: 136712kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
result:
ok 1000000 lines