UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215042#2037. awujiachen606ms1220kbC++2.7kb2024-11-25 20:58:082024-11-25 23:10:30

answer

/*#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int ll[1000005],rr[1000005];
int ll1[1000005],rr1[1000005];
stack<int> st;
int main(){
    string s;
    cin>>s;
    int cnt=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            cnt++;
            st.push(i+1);
        }
        else if(cnt){
            cnt--;
            ll1[st.top()]=i+1;
            st.pop();
            ll[i+1]+=2;
        }
        ll[i+1]+=ll[i];
    }
    while(st.size()){
        st.pop();
    }
    cnt=0;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]==')'){
            cnt++;
            st.push(i+1);
        }
        else if(cnt){
            cnt--;
            rr1[st.top()]=i+1;
            st.pop();
            rr[i+1]+=2;
        }
        rr[i+1]+=rr[i+2];
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,r,ans=0;
        scanf("%d%d",&l,&r);
        ans=ll[s.size()]-ll[l-1]-rr[r+1];
        if(l!=1){
            if((s[l-2]=='('&&(ll1[l-1]>=l&&ll1[l-1]<=r))||(s[l-1]==')'&&rr1[l]))ans-=2;
        }
        if(r!=s.size()){
            if((s[r]==')'&&(rr1[r+1]>=l&&rr1[r+1]<=r))||(s[r-1]=='('&&ll1[r]))ans-=2;
        }
        if(l!=1&&r!=s.size()&&s[l-2]=='('&&ll1[l-1]==r+1)ans-=2;
        printf("%d\n",ans);
    }
}*/
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1e6+5;
const ll mod=1e9+7;
const double eps=1e-5;
//const double pi=acos(-1);
 
#define ls p<<1
#define rs p<<1|1
 
char s[N];
struct seg{
    int l,r,mx;
}t[N<<2];
void build(int p,int l,int r){
    if(l==r){
        t[p].l=s[l]=='(';
        t[p].r=s[l]==')';
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    int x=min(t[ls].l,t[rs].r);
    t[p].mx=t[ls].mx+x+t[rs].mx;
    t[p].l=t[ls].l-x+t[rs].l;
    t[p].r=t[ls].r+t[rs].r-x;
}
seg ask(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
        return t[p];
    int mid=l+r>>1;
    if(y<=mid)
        return ask(ls,l,mid,x,y);
    else if(x>mid)
        return ask(rs,mid+1,r,x,y);
    else
    {
        seg ans;
        seg lx=ask(ls,l,mid,x,y);
        seg rx=ask(rs,mid+1,r,x,y);
        int use=min(lx.l,rx.r);
        ans.mx=lx.mx+rx.mx+use;
        ans.l=lx.l+rx.l-use;
        ans.r=lx.r+rx.r-use;
        return ans;
    }
}
int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int n,m;
    cin>>(s+1);
    cin>>m;
    n=strlen(s+1);
    build(1,1,n);
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        printf("%d\n",ask(1,1,n,l,r).mx*2);
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1216kb

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: 1220kb

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: 1220kb

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: 1220kb

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: 1216kb

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: 1216kb

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...

result: