ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#192673 | #2037. a | snow_trace | 100 | 2636ms | 57136kb | C++11 | 1.9kb | 2023-10-10 11:31:22 | 2023-10-10 12:12:18 |
answer
#include<bits/stdc++.h>
using namespace std;
char s[1000005];int n,q;
vector<pair<int,int> >query[1000005];
int ans[1000005],suf[1000005],pre[1000005],ex1[1000005],ex2[1000005];
void solve(int l,int r){
if(l == r){
for(int i =0;i<query[l].size();i++)ans[query[l][i].second] = 0;query[l].clear();return;
}int mid = l+r>>1;
solve(mid+1,r);int tot =0 ;
pre[0] = suf[0] = ex1[0] = ex2[0] = 0;
for(int i = mid;i>=l;i--){
pre[mid-i+1] = pre[mid-i],ex1[mid-i+1] = ex1[mid-i];
if(s[i] == ')'){
tot++;
}else{
if(tot)tot--,pre[mid-i+1]+=2;
else ex1[mid-i+1]++;
}
}tot = 0;
for(int i = mid+1;i<=r;i++){
suf[i-mid] = suf[i-mid-1],ex2[i-mid] = ex2[i-mid-1];
if(s[i] == '(')tot++;
else{
if(tot)tot--,suf[i-mid]+=2;
else ex2[i-mid]++;
}
}for(int i = mid;i>=l;i--){
int cnt =0 ;
for(int j = query[i].size()-1;j>=0;j--){
if(query[i][j].first<=mid)break;cnt++;
assert(query[i][j].first<=r);
int rr = query[i][j].first;
ans[query[i][j].second] = 2*min(ex1[mid-i+1],ex2[rr-mid])+pre[mid-i+1]+suf[rr-mid];
// cout << i << " " << query[i][j].first << " " << ans[query[i][j].second] << " " << mid << " " << pre[mid-i+1] << " " << suf[rr-mid] << endl;
}for(int j =0;j<cnt;j++)query[i].pop_back();
}solve(l,mid);
}inline void write(int x){
if(x>=10)write(x/10);
putchar(x%10+'0');
}inline int read(){
int x = 0;char c= getchar();
while(c<'0' or c>'9')c = getchar();
while('0'<=c and c<='9')x = x*10+(c^48),c = getchar();
return x;
}
signed main(){
// freopen("in.txt","r",stdin);
scanf("%s",s+1);q = read();n = strlen(s+1);
// for(int i = 1;i<=n;i++)cout << s[i];cout << endl;
for(int i = 1;i<=q;i++){
int l = read(),r = read();
query[l].push_back(make_pair(r,i));
}for(int i = 1;i<=n;i++)sort(query[i].begin(),query[i].end());
solve(1,n);
for(int i = 1;i<=q;i++){
write(ans[i]);putchar('\n');
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 4ms
memory: 24680kb
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: 3ms
memory: 24684kb
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: 6ms
memory: 24688kb
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: 4ms
memory: 24684kb
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: 9ms
memory: 24684kb
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: 24680kb
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: 648ms
memory: 57136kb
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: 657ms
memory: 57128kb
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: 646ms
memory: 57128kb
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: 659ms
memory: 57136kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
result:
ok 1000000 lines