UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215019#2037. awangyaxu12306385ms157148kbC++111.9kb2024-11-25 19:58:192024-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...