NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #215044 | #2037. a | fddwd | 60 | 45ms | 24772kb | C++11 | 930b | 2024-11-25 21:00:49 | 2024-11-25 23:10:52 |
answer
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
#define pint pair<int,int>
#define fir first
#define sec second
int q,len,l[MAXN],r[MAXN],p[MAXN],c[MAXN],ans[MAXN];
string s;
vector<pint>spt[MAXN];
inline int lowbit(int &i){
return i&-i;
}inline void modify(int i,int delta){
for(;i<=len;i+=lowbit(i)) c[i]+=delta;
}inline int query(int i){
int sum=0;for(;i;i-=lowbit(i)) sum+=c[i];return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>s>>q;len=s.length();s=' '+s;
for(int i=1;i<=q;++i) cin>>l[i]>>r[i],spt[l[i]].push_back({r[i],i});
stack<int>stk;
for(int i=1;i<=len;++i)
if(s[i]=='(') stk.push(i);
else if(!stk.empty()) p[stk.top()]=i,stk.pop();
for(int i=len;i>=1;--i){
if(p[i]) modify(p[i],1);
for(int j=0;j<spt[i].size();++j)
ans[spt[i][j].sec]=2*query(spt[i][j].fir);
}for(int i=1;i<=q;++i) cout<<ans[i]<<endl;
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 9ms
memory: 24772kb
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: 24768kb
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: 3ms
memory: 24768kb
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: 19ms
memory: 24768kb
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: 3ms
memory: 24772kb
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: 4ms
memory: 24768kb
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: 0
Time Limit Exceeded
input:
((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...
output:
142860 235344 446706 759772 134088 748980 83870 685562 31730 572204 366368 67746 18554 603330 946486...
result:
Test #8:
score: 0
Time Limit Exceeded
input:
())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...
output:
583148 425884 255036 448502 200322 256890 167684 114904 55236 440164 138094 879918 580038 452166 984...
result:
Test #9:
score: 0
Time Limit Exceeded
input:
)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...
output:
47942 241400 323510 553980 111490 20570 51892 169422 82080 124416 107806 804528 123414 274334 135650...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
