ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214992 | #2037. a | erican | 60 | 41ms | 63740kb | C++11 | 2.2kb | 2024-11-25 19:26:47 | 2024-11-25 23:03:34 |
answer
/* Erica N */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
int xx = 0, ff = 1;char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
// void write(int out) {
// if (out < 0)
// putchar('-'), out = -out;
// if (out > 9)
// write(out / 10);
// putchar(out % 10 + '0');
// }
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
const int N = 1e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
string s;
namespace SGT{
pii t[N<<2];
pii merge(pii a,pii b){
int p=min(a.pf,b.ps);
return make_pair(a.pf+b.pf-p,a.ps+b.ps-p);
}
void build(int x,int l,int r){
if(l==r){
// cdbg(s[l],l);
if(s[l]==')')t[x]={0,1};
else t[x]={1,0};
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x]=merge(t[x<<1],t[x<<1|1]);
}
pii query(int x,int l,int r,int pl,int pr){
if(pl<=l&&pr>=r)return t[x];
int mid=l+r>>1;
if(pr<=mid)return query(x<<1,l,mid,pl,pr);
if(pl>mid)return query(x<<1|1,mid+1,r,pl,pr);
return merge( query(x<<1,l,mid,pl,pr),query(x<<1|1,mid+1,r,pl,pr));
}
}using namespace SGT;
signed main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>s;
int n=s.size();
s=" "+s;
build(1,1,n);
int q=rd;
while(q--){
int l=rd,r=rd;
pii p=query(1,1,n,l,r);
// cdbg(l,r,p.pf,p.ps);
cout<<r-l+1-p.pf-p.ps<<endl;
}
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 4ms
memory: 63736kb
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: 16ms
memory: 63740kb
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: 63736kb
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: 10ms
memory: 63736kb
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: 8ms
memory: 63740kb
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: 3ms
memory: 63736kb
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...