ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215042 | #2037. a | wujiachen | 60 | 6ms | 1220kb | C++ | 2.7kb | 2024-11-25 20:58:08 | 2024-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...