ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215039 | #2037. a | whereismy25 | 60 | 7ms | 5208kb | C++ | 2.0kb | 2024-11-25 20:48:07 | 2024-11-25 23:10:19 |
answer
/*****************************************
Note :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#define LL long long
#define IL inline
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
using namespace std;
IL int read()
{
char ch = getchar();
int f = 1, num = 0;
while(ch>'9'||ch<'0')
{
if(ch=='-') f = -1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
num = num*10+ch-'0', ch = getchar();
return num*f;
}
int n,q;
int mn[N],stk[N],tp;
string s;
int rt[N],ls[N*4],rs[N*4],sum[N*4],tot;
void upd(int la,int ne,int l,int r,int x)
{
sum[ne]=sum[la]+1;
if(l==r)
return;
ls[ne]=ls[la],rs[ne]=rs[la];
int mid=l+r>>1;
if(x<=mid)
{
ls[ne]=++tot;
upd(ls[la],ls[ne],l,mid,x);
}
else
{
rs[ne]=++tot;
upd(rs[la],rs[ne],mid+1,r,x);
}
}
int qsum(int la,int ne,int l,int r,int L,int R)
{
// printf("%d %d %d %d\n",l,r,sum[ne],sum[la]);
if(L<=l&&r<=R)
return sum[ne]-sum[la];
int mid=l+r>>1,res=0;
if(L<=mid)
res+=qsum(ls[la],ls[ne],l,mid,L,R);
if(R>mid)
res+=qsum(rs[la],rs[ne],mid+1,r,L,R);
return res;
}
int main()
{
cin>>s;
n=s.size();
memset(mn,0x3f,sizeof(mn));
for(int i = 0;i<n;i++)
{
if(s[i]=='(')
stk[++tp]=i+1;
else
{
if(tp)
mn[stk[tp--]]=i+1;
}
}
rt[0]=++tot;
for(int i = 1;i<=n;i++)
{
if(mn[i]<=n)
{
rt[i]=++tot;
upd(rt[i-1],rt[i],1,n,mn[i]);
// printf("%d %d\n",i,mn[i]);
}
else rt[i]=rt[i-1];
}
q=read();
while(q--)
{
int l=read(),r=read();
// printf("rt:%d %d\n",rt[l-1],rt[r]);
int res=qsum(rt[l-1],rt[r],1,n,1,r)*2;
printf("%d\n",res);
}
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 3ms
memory: 5204kb
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: 2ms
memory: 5204kb
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: 5208kb
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: 5204kb
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: 5204kb
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: 2ms
memory: 5208kb
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
Runtime Error
input:
((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...
output:
result:
Test #8:
score: 0
Runtime Error
input:
())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...
output:
result:
Test #9:
score: 0
Runtime Error
input:
)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...
output:
result:
Test #10:
score: 0
Runtime Error
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...