Submission #1097746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097746		vjudge1	Inside information (BOI21_servers)	C++14	100 / 100	546 ms	96084 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;
}
int clone(int x){
    tr[++tot]=tr[x];
    return tot;
}
int modify(int x,int l,int r,int pos,int k){
    x=clone(x);
    if(l==r){
        tr[x].sum+=k;
        return x;
    }
    int mid=(l+r)/2;
    if(pos<=mid)tr[x].ls=modify(tr[x].ls,l,mid,pos,k);
    else tr[x].rs=modify(tr[x].rs,mid+1,r,pos,k);
    pushup(x);
    return x;
}
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)return 0;
    if(l>R||r<L)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(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        rt[i]=modify(rt[0],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=1;i<=tot;i++)tr[i]={0,0,0};
    tot=0;
    memset(rt,0,sizeof rt);
    for(int i=1;i<=n;i++)rt[i]=modify(rt[0],1,n+m-1,i,0);
    for(int i=n+m-1;i>=1;i--){
        if(tim[i]=='S'){
            rt[xi[i]]=modify(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]];
        }
    }

    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