ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214985 | #2037. a | STASISZHY | 100 | 4541ms | 35036kb | C++11 | 1.7kb | 2024-11-25 19:14:08 | 2024-11-25 23:02:11 |
answer
// Problem: A. a
// Contest: undefined - NOIP2024训练赛 13
// URL: http://noi.ac/contest/1165/problem/2037
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
const int N = 1e6 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m, q, ans;
struct Tree
{
int l, r, suml, sumr;
}tr[N << 2];
string s;
inline void pushup(int x)
{
tr[x].suml = tr[2 * x].suml + tr[2 * x + 1].suml - min(tr[2 * x].suml, tr[2 * x + 1].sumr);
tr[x].sumr = tr[2 * x].sumr + tr[2 * x + 1].sumr - min(tr[2 * x].suml, tr[2 * x + 1].sumr);
}
void build(int x, int l, int r)
{
tr[x].l = l, tr[x].r = r;
if(l == r)
{
tr[x].suml = (s[l] == '(');
tr[x].sumr = (s[r] == ')');
return;
}
int mid = l + r >> 1;
build(2 * x, l, mid);
build(2 * x + 1, mid + 1, r);
pushup(x);
}
inline Tree merge(Tree ls, Tree rs)
{
Tree res = {ls.l, rs.r, 0, 0};
res.suml = ls.suml + rs.suml - min(ls.suml, rs.sumr);
res.sumr = ls.sumr + rs.sumr - min(ls.suml, rs.sumr);
return res;
}
Tree query(int x, int l, int r)
{
if(tr[x].l >= l && tr[x].r <= r) return tr[x];
int mid = tr[x].l + tr[x].r >> 1;
if(l > mid) return query(2 * x + 1, l, r);
else if(r <= mid) return query(2 * x, l, r);
else return merge(query(2 * x, l, r), query(2 * x + 1, l, r));
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> s; n = s.size(), s = ' ' + s;
build(1, 1, n);
cin >> q;
while(q --)
{
int l, r; cin >> l >> r;
Tree now = query(1, l, r);
cout << r - l + 1 - now.suml - now.sumr << '\n';
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1308kb
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: 1308kb
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: 1ms
memory: 1304kb
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: 1304kb
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: 0ms
memory: 1308kb
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: 1308kb
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: 10
Accepted
time: 1135ms
memory: 35036kb
input:
((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...
output:
142860 235344 446706 759772 134088 748980 83870 685562 31730 572204 366368 67746 18554 603330 946486...
result:
ok 1000000 lines
Test #8:
score: 10
Accepted
time: 1137ms
memory: 35036kb
input:
())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...
output:
583148 425884 255036 448502 200322 256890 167684 114904 55236 440164 138094 879918 580038 452166 984...
result:
ok 1000000 lines
Test #9:
score: 10
Accepted
time: 1126ms
memory: 35032kb
input:
)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...
output:
47942 241400 323510 553980 111490 20570 51892 169422 82080 124416 107806 804528 123414 274334 135650...
result:
ok 1000000 lines
Test #10:
score: 10
Accepted
time: 1142ms
memory: 35036kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
487878 425694 419984 176404 493462 782462 63276 27548 109942 308166 354282 302574 697816 3128 144748...
result:
ok 1000000 lines