Submission #1097747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097747		vjudge1	Inside information (BOI21_servers)	C++14	100 / 100	349 ms	55380 KiB

servers

#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
struct node{
    int ls,rs,sum;
}tr[MAXN*400];
int tot=0;
int rt[MAXN],xi[MAXN],yi[MAXN];
char tim[MAXN];
bool ans[MAXN];
void pushup(int x){
    int l=tr[x].ls,r=tr[x].rs;
    tr[x].sum=tr[l].sum+tr[r].sum;
    //cout<<tr[x].sum<<endl;
}
int clone(int x){
    tr[++tot]=tr[x];
    return tot;
}
void modify(int pre,int &v,int l,int r,int x,int k){
	v=clone(pre);
	if(l==r){
		tr[v].sum+=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)modify(tr[pre].ls,tr[v].ls,l,mid,x,k);
	else modify(tr[pre].rs,tr[v].rs,mid+1,r,x,k); 
	pushup(v);
}
int merge(int x,int y,int l,int r){
    if(!x)return y;
    if(!y)return x;
    int nd=clone(0);
    if(l==r){
        tr[nd].sum=tr[x].sum+tr[y].sum;
        return nd;
    }
    int mid=(l+r)/2;
    tr[nd].ls=merge(tr[x].ls,tr[y].ls,l,mid);
    tr[nd].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
    pushup(nd);
    return nd;
}
int query(int x,int l,int r,int pos){
    if(l==r)return tr[x].sum;
    int mid=(l+r)/2;
    if(pos<=mid)return query(tr[x].ls,l,mid,pos);
    else return query(tr[x].rs,mid+1,r,pos);
}
int qsum(int x,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        return tr[x].sum;
    }
    if(l>R||r<L)return 0;
    if(l>r)return 0;
    if(!x)return 0;
    int mid=(l+r)/2;
    int sum=0;
    sum+=qsum(tr[x].ls,l,mid,L,R);
    sum+=qsum(tr[x].rs,mid+1,r,L,R);
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        modify(rt[0],rt[i],1,n,i,1);
    }

    for(int i=1;i<=n+m-1;i++){
        char str;
        cin>>str;tim[i]=str;
        if(str=='S'){
            cin>>xi[i]>>yi[i];
            
            rt[xi[i]]=merge(rt[xi[i]],rt[yi[i]],1,n);
            rt[yi[i]]=rt[xi[i]];
            
        }else if(str=='Q'){
            cin>>xi[i]>>yi[i];
            ans[i]=query(rt[xi[i]],1,n,yi[i]);
        }else{
            cin>>xi[i];
        }
    }
    for(int i=0;i<=tot;i++)tr[i]={0,0,0};
    tot=0;
    memset(rt,0,sizeof rt);
    for(int i=1;i<=n;i++)rt[i]=++tot;
    for(int i=n+m-1;i>=1;i--){
        if(tim[i]=='S'){
            modify(rt[xi[i]],rt[xi[i]],1,n+m-1,i,1);
            rt[xi[i]]=merge(rt[xi[i]],rt[yi[i]],1,n+m-1);
            rt[yi[i]]=rt[xi[i]];
            //cout<<rt[xi[i]]<<endl;
        }
    }

    for(int i=1;i<=n+m-1;i++){
        if(tim[i]=='Q'){
            if(ans[i])cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }else if(tim[i]=='C'){
            cout<<(qsum(rt[xi[i]],1,n+m-1,1,i)+1)<<endl;
        }
    }
    return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5