ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215019 | #2037. a | wangyaxu123 | 0 | 6385ms | 157148kb | C++11 | 1.9kb | 2024-11-25 19:58:19 | 2024-11-25 23:07:10 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
#include<cstring>
#include<stack>
using namespace std;
#define int long long
const int N=1e6+10;
char s[N];
int q,n,last[N],aa[N];
vector<int> v[N],vv[N];
struct mm{
int l,r,id;
}a[N];
struct mmm{
int l,r,mx;
}t[4*N];
struct node{
int id;
char s;
};
bool cmp(mm x,mm y){
return x.r<y.r;
}
stack<node> ss;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
void build(int p,int l,int r){
t[p].l=l;
t[p].r=r;
t[p].mx=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void pushup(int p){
t[p].mx=t[p*2].mx+t[p*2+1].mx;
}
void change(int p,int pos,int val){
if(t[p].l==t[p].r&&t[p].l==pos){
t[p].mx=val;
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(pos<=mid)
change(p*2,pos,val);
else
change(p*2+1,pos,val);
pushup(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r)
return t[p].mx;
int mid=(t[p].l+t[p].r)>>1,ans=0;
if(l<=mid)
ans+=query(p*2,l,r);
if(r>mid)
ans+=query(p*2+1,l,r);
return ans;
}
signed main(){
cin>>(s+1);
n=strlen(s+1);
node xxx;
xxx.s='a';
xxx.id=0;
ss.push(xxx);
for(int i=1;i<=n;i++){
last[i]=0;
bool ff=0;
if(s[i]==')'){
node x;
x=ss.top();
if(x.s=='('){
last[i]=x.id;
ss.pop();
ff=1;
}
}
node xx;
xx.s=s[i];
xx.id=i;
if(ff==0)
ss.push(xx);
}
q=read();
for(int i=1;i<=n;i++)
cout<<last[i]<<" ";
for(int i=1;i<=q;i++){
a[i].l=read();
a[i].r=read();
a[i].id=i;
v[a[i].r].push_back(i);
}
build(1,1,n);
for(int i=1;i<=n;i++){
change(1,last[i],2);
for(int j=0;j<v[i].size();j++){
int x=v[i][j];
aa[a[x].id]=query(1,a[x].l,n);
}
}
for(int i=1;i<=q;i++){
cout<<aa[i]<<'\n';
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 48236kb
input:
(()))())))(())()())()()))((((()()))((((()((())()))(()((((()(())(())(()))())()())()())(())(()()((((((...
output:
0 0 2 1 0 0 6 0 0 0 0 0 12 11 0 15 0 17 0 0 20 0 22 0 0 0 0 0 0 0 30 0 32 29 28 0 0 0 0 0 40 0 0 0 4...
result:
wrong answer 1st lines differ - expected: '854', found: '0 0 2 1 0 0 6 0 0 0 0 0 12 11 ...0 0 992 0 ...
Test #2:
score: 0
Wrong Answer
time: 9ms
memory: 48240kb
input:
)))((()())((())((()()())())(((())())((()((())(())()((((((())))((()(()())))(()()(())())()))(()()))(((...
output:
0 0 0 0 0 0 6 0 8 5 0 0 0 13 12 0 0 0 18 0 20 0 22 17 0 25 16 0 0 0 0 31 30 0 34 29 0 0 0 39 0 0 0 4...
result:
wrong answer 1st lines differ - expected: '30', found: '0 0 0 0 0 0 6 0 8 5 0 0 0 13 1... 977 0 993 ...
Test #3:
score: 0
Wrong Answer
time: 9ms
memory: 48236kb
input:
(()((())))))))((())(()()))()))()()())(()))(())))))))(((())((((((((((()((()())()(()(())(()())(()))(((...
output:
0 0 2 0 0 0 6 5 4 1 0 0 0 0 0 0 0 17 16 0 0 21 0 23 20 15 0 27 0 0 0 31 0 33 0 35 0 0 0 39 38 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '674', found: '0 0 2 0 0 0 6 5 4 1 0 0 0 0 0 ...6 0 0 0 99...
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 48236kb
input:
))))))))()))())()(()()())()())(((()())(((()(((()()))(()()()))())(()()(()()())()(())()())))))()((((()...
output:
0 0 0 0 0 0 0 0 0 9 0 0 0 13 0 0 16 0 0 19 0 21 0 23 18 0 26 0 28 0 0 0 0 0 34 0 36 33 0 0 0 0 42 0 ...
result:
wrong answer 1st lines differ - expected: '168', found: '0 0 0 0 0 0 0 0 0 9 0 0 0 13 0...262 261 0 ...
Test #5:
score: 0
Wrong Answer
time: 12ms
memory: 48240kb
input:
((())))(()((()()))()))))((((()()()()()()()))()()(()(())(()((()))()((())))))()(((()())()))()())))(())...
output:
0 0 0 3 2 1 0 0 0 9 0 0 0 13 0 15 12 11 0 19 8 0 0 0 0 0 0 0 0 29 0 31 0 33 0 35 0 37 0 39 0 41 28 2...
result:
wrong answer 1st lines differ - expected: '634', found: '0 0 0 3 2 1 0 0 0 9 0 0 0 13 0...981 846 84...
Test #6:
score: 0
Wrong Answer
time: 8ms
memory: 48236kb
input:
))((()))()(())())(()()))))()()((((()()())()((())(())))))(())))()())()()(())()(())())(()())))(()()))(...
output:
0 0 0 0 0 5 4 3 0 9 0 0 12 11 0 15 0 0 0 19 0 21 18 0 0 0 0 27 0 29 0 0 0 0 0 35 0 37 0 39 34 0 42 0...
result:
wrong answer 1st lines differ - expected: '728', found: '0 0 0 0 0 5 4 3 0 9 0 0 12 11 ...0 0 0 0 99...
Test #7:
score: 0
Wrong Answer
time: 1582ms
memory: 157144kb
input:
((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...
output:
0 0 0 0 0 5 4 3 0 9 0 11 0 13 2 0 0 17 16 1 0 0 0 23 0 25 22 0 0 0 0 31 30 29 28 0 0 37 0 0 0 41 40 ...
result:
wrong answer 1st lines differ - expected: '142860', found: '0 0 0 0 0 5 4 3 0 9 0 11 0 13 ...0 99999...
Test #8:
score: 0
Wrong Answer
time: 1615ms
memory: 157148kb
input:
())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...
output:
0 1 0 0 0 0 6 0 0 0 0 0 0 13 12 0 0 17 0 19 0 0 0 23 0 0 26 25 22 0 0 0 32 31 30 0 0 0 0 39 38 0 0 0...
result:
wrong answer 1st lines differ - expected: '583148', found: '0 1 0 0 0 0 6 0 0 0 0 0 0 13 1... 0 0 0 ...
Test #9:
score: 0
Wrong Answer
time: 1553ms
memory: 157148kb
input:
)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...
output:
0 0 2 0 0 0 6 0 8 5 0 0 12 11 0 15 4 0 0 19 0 21 18 0 0 0 0 0 0 29 0 31 28 0 34 0 36 0 0 0 0 0 0 43 ...
result:
wrong answer 1st lines differ - expected: '47942', found: '0 0 2 0 0 0 6 0 8 5 0 0 12 11 ...9991 999...
Test #10:
score: 0
Wrong Answer
time: 1587ms
memory: 157132kb
input:
())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...
output:
0 1 0 0 4 0 6 0 0 9 0 11 8 0 0 0 16 0 0 19 0 0 0 0 0 0 0 0 0 29 0 0 0 33 0 35 0 0 0 0 40 39 38 0 0 4...
result:
wrong answer 1st lines differ - expected: '487878', found: '0 1 0 0 4 0 6 0 0 9 0 11 8 0 0...0 99999...