UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215006#2037. aa_sad_soul08484ms35464kbC++112.0kb2024-11-25 19:46:242024-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'