ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215006 | #2037. a | a_sad_soul | 0 | 8484ms | 35464kb | C++11 | 2.0kb | 2024-11-25 19:46:24 | 2024-11-25 23:05:56 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,q;
const int MAXN = 1e6+10;
char s[MAXN];
int pl[MAXN],pr[MAXN];
vector<int>is;
struct node{
int l,r;
int sum;
}tree[MAXN<<2];
#define ls(p)(p<<1)
#define rs(p)(p<<1|1)
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r;int mid=(l+r)>>1;
if(l==r){
return ;
}build(ls(p),l,mid),build(rs(p),mid+1,r);
}
void Insert(int p,int id,int v){
int l=tree[p].l,r=tree[p].r,mid=(l+r)>>1;
if(l==r){tree[p].sum=v;return ;}
if(id<=mid)Insert(ls(p),id,v);
else Insert(rs(p),id,v);
tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
}
int query(int p,int L,int R){
if(L>R)return 0;
int l=tree[p].l,r=tree[p].r,mid=(l+r)>>1;
if(L<=l&&r<=R)return tree[p].sum;
if(L<=mid&&mid<R)return query(ls(p),L,R)+query(rs(p),L,R);
if(L<=mid)return query(ls(p),L,R);
return query(rs(p),L,R);
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;++i){
if(s[i]==')')continue;
if(s[i]=='(')pl[i]++;
if(s[i-1]=='(')pl[i]+=pl[i-1];
}
for(int i=n;i;i--){
if(s[i]=='(')continue;
if(s[i]==')')pr[i]++;
if(s[i+1]==')')pr[i]+=pr[i+1];
}
build(1,1,n);
for(int i=1;i<=n;++i){
if(pl[i]&&pr[i+1])is.push_back(i),Insert(1,i,2*min(pl[i],pr[i+1]));
}
scanf("%d",&q);
while(q--){
int l,r;scanf("%d%d",&l,&r);
int p1=lower_bound(is.begin(),is.end(),l)-is.begin(),p2=upper_bound(is.begin(),is.end(),r)-is.begin()-1;
if(p1>p2){
puts("0");continue;
}int ans1=0,ans2=0,ans3=0;
int a=is[p1],b=is[p2];
if(p1==p2){
ans1=min(min(a-l+1,pl[a]),min(r-a,pr[a+1]))*2;
printf("%d\n",ans1);continue;
}
ans1=min(min(a-l+1,pl[a]),min(r-a,pr[a+1]))*2;
ans2=min(min(b-l+1,pl[b]),min(r-b,pr[b+1]))*2;
ans3=query(1,a+1,b-1);
printf("%d\n",ans1+ans2+ans3);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1300kb
input:
(()))())))(())()())()()))((((()()))((((()((())()))(()((((()(())(())(()))())()())()())(())(()()((((((...
output:
572 96 80 12 562 152 380 182 354 198 164 250 552 326 116 188 370 344 318 76 120 8 564 214 222 180 25...
result:
wrong answer 1st lines differ - expected: '854', found: '572'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 1296kb
input:
)))((()())((())((()()())())(((())())((()((())(())()((((((())))((()(()())))(()()(())())()))(()()))(((...
output:
20 18 66 276 188 124 282 42 332 80 426 328 82 42 238 174 238 12 110 144 230 34 262 340 58 342 36 312...
result:
wrong answer 1st lines differ - expected: '30', found: '20'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 1300kb
input:
(()((())))))))((())(()()))()))()()())(()))(())))))))(((())((((((((((()((()())()(()(())(()())(()))(((...
output:
488 142 78 116 148 172 276 538 128 158 154 430 292 202 176 268 162 340 124 320 144 494 178 172 566 2...
result:
wrong answer 1st lines differ - expected: '674', found: '488'
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 1300kb
input:
))))))))()))())()(()()())()())(((()())(((()(((()()))(()()()))())(()()(()()())()(())()())))))()((((()...
output:
120 264 194 274 382 226 50 342 512 202 138 282 50 324 284 140 138 426 134 106 636 300 372 40 76 308 ...
result:
wrong answer 1st lines differ - expected: '168', found: '120'
Test #5:
score: 0
Wrong Answer
time: 1ms
memory: 1296kb
input:
((())))(()((()()))()))))((((()()()()()()()))()()(()(())(()((()))()((())))))()(((()())()))()())))(())...
output:
442 280 258 6 172 266 156 294 196 114 186 320 220 84 384 92 422 558 88 116 56 340 178 110 20 228 384...
result:
wrong answer 1st lines differ - expected: '634', found: '442'
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 1296kb
input:
))((()))()(())())(()()))))()()((((()()())()((())(())))))(())))()())()()(())()(())())(()())))(()()))(...
output:
510 180 400 158 552 112 198 152 0 480 184 218 446 226 582 334 278 514 66 104 286 318 104 12 204 546 ...
result:
wrong answer 1st lines differ - expected: '728', found: '510'
Test #7:
score: 0
Wrong Answer
time: 2113ms
memory: 35460kb
input:
((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...
output:
95456 157344 298512 507110 89750 500094 56172 457902 21346 382202 244386 45204 12394 403172 631638 6...
result:
wrong answer 1st lines differ - expected: '142860', found: '95456'
Test #8:
score: 0
Wrong Answer
time: 2214ms
memory: 35460kb
input:
())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...
output:
390382 284760 170368 300136 134538 172126 111938 77286 37142 294470 92696 588618 388370 303214 65752...
result:
wrong answer 1st lines differ - expected: '583148', found: '390382'
Test #9:
score: 0
Wrong Answer
time: 2105ms
memory: 35464kb
input:
)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...
output:
31960 160936 216670 370288 74484 13858 34852 113570 55236 83236 72004 536856 82508 182488 90826 4780...
result:
wrong answer 1st lines differ - expected: '47942', found: '31960'
Test #10:
score: 0
Wrong Answer
time: 2050ms
memory: 35464kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
325656 284008 281034 118204 329266 522422 42614 18556 73334 205328 236954 202258 465640 2154 96962 1...
result:
wrong answer 1st lines differ - expected: '487878', found: '325656'