UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215060#2037. aN603ms1480kbC++113.5kb2024-11-25 22:13:192024-11-25 23:12:28

answer

//
//  na 2037.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/25.
//

#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;
#ifdef MAC_OS_VERSION_11_0
const int maxn = 1e3 + 5, maxdep = 20;
#else
const int maxn = 1e6 + 5, maxdep = 20;
#endif
int n, q, sm[maxn], st[maxn][maxdep], lg2[maxn], nxt[maxn][maxdep], las[maxn][maxdep], sl[maxn], sr[maxn];
char s[maxn];
inline void init_sums(){
    for(int i = 1; i <= n; ++i){
        sm[i] = sm[i - 1] + (s[i] == '('? 1: -1);
        sl[i] = sl[i - 1] + (s[i] == '(');
        sr[i] = sr[i - 1] + (s[i] == ')');
    }
}
inline void init_st(){
    for(int i = n; i; --i){
        st[i][0] = sm[i];
        for(int j = 1; j < maxdep; ++j)
            st[i][j] = min(st[i][j - 1], st[min(n, i + (1 << (j - 1)))][j - 1]);
    }
    lg2[1] = 0;
    for(int i = 2; i <= n; ++i)
        lg2[i] = lg2[i >> 1] + 1;
}
inline int query(int lt, int rt){
    int dep = lg2[rt - lt + 1];
    return min(st[lt][dep], st[rt - (1 << dep) + 1][dep]);
}
inline void init_chain(){
    int ls = 0;
    for(int i = 1; i <= n + 1; ++i){
        las[i][0] = ls;
        for(int j = 1; j < maxdep; ++j)
            las[i][j] = las[las[i][j - 1]][j - 1];
        if(s[i] == ')')
            ls = i;
    }
    for(int i = 0; i < maxdep; ++i)
        nxt[n + 1][i] = n + 1;
    ls = n + 1;
    for(int i = n; i >= 0; --i){
        nxt[i][0] = ls;
        for(int j = 1; j < maxdep; ++j)
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        if(s[i] == '(')
            ls = i;
    }
}
inline void readint(int &v){
    v = 0;
    char r = getchar();
    while(r - 48 >= 10u)
        r = getchar();
    do{
        v = (v << 1) + (v << 3) + (r ^ 48);
        r = getchar();
    }while(r - 48 < 10u);
}
namespace qprintint{
char buf[15];
inline void printint(int v){
    int p = 0;
    while(v){
        buf[p++] = (v % 10) ^ 48;
        v /= 10;
    }
    if(!p)
        putchar('0');
    else{
        while(p--)
            putchar(buf[p]);
    }
}
}
using qprintint::printint;
inline void solve(int l, int r){
//    cerr << "solve " << l << " -> " << r << endl;
    int lim = min(sl[r] - sl[l - 1], sr[r] - sr[l - 1]), ans = 0, ra;
//    cerr << "never exceeds " << lim << endl;
    int lst = l - (s[l] == '('), rst = r + (s[r] == ')'), lp, rp;
    for(int i = maxdep - 1, d = 1 << (maxdep - 1); i >= 0; --i, d >>= 1)
        if((ra = ans + d) <= lim){
//            cerr << "  try " << ans << " -> " << ra << endl;
            lp = nxt[lst][i];
            rp = las[rst][i];
//            cerr << "    lp: " << lst << " -> " << lp << endl;
//            cerr << "    rp: " << rst << " -> " << rp << endl;
//            if(lp >= rp){
//                cerr << "      max neg: " << -(query(rp, lp) - sm[rp - 1]) << ", base: " << sl[rp - 1] - sl[l - 1] << endl;
//            }
            if(lp < rp || -(query(rp, lp) - sm[rp - 1]) <= sl[rp - 1] - sl[l - 1]){
//                cerr << "  success" << endl;
                ans = ra;
                lst = lp;
                rst = rp;
            }
        }
    printint(ans << 1);
    putchar('\n');
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    while(true){
        char r = getchar();
        if(r != '(' && r != ')')
            break;
        s[++n] = r;
    }
    readint(q);
    init_sums();
    init_st();
    init_chain();
    while(q--){
        int l, r;
        readint(l); readint(r);
        solve(l, r);
    }
    fflush(stdout);
    return 0;
}

详细

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

Test #1:

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

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

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: 0ms
memory: 1476kb

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: 1ms
memory: 1476kb

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: 1ms
memory: 1480kb

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: 1ms
memory: 1480kb

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: