ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215060 | #2037. a | N | 60 | 3ms | 1480kb | C++11 | 3.5kb | 2024-11-25 22:13:19 | 2024-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...