Submission #899287

#	Time	Username	Problem	Language	Result	Execution time	Memory
899287		AIF_is_carving	Inside information (BOI21_servers)	C++17	10 / 100	52 ms	9808 KiB

servers

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const int N=2e5+5;

vector<pair<int,int>>graph(N); 
vector<pair<int,int>>cnt(N); 

ll cf(ll x,ll y){
    if(x%y==0){
        return x/y;
    }else{
        return x/y+1;
    }
}

const int M=5e5+5;
int nodes[M];
int a[M];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k; cin>>n>>k;

    for(int i=1; i<=n; i++){
        graph[i]={i, i};
        cnt[i]={i,i};
    }

    int x=n, power=0;
    while(x>1){
        x=cf(x,2);
        power+=1;
    }
    int size=1;
    for(int i=0; i<power; i++){
        size*=2;
    }

    for(int i=0; i<size; i++){
        a[i+1]=0;
    }

    nodes[1]=1;


    for(int i=0; i<n+k-1; i++){
        char c; cin>>c;

        if(c=='S'){ 
           int u, v;
           cin>>u>>v;
           int a=graph[min(u,v)].first;
           int b=graph[max(u,v)].second;

           graph[u]={a,b};
           graph[v]={a,b};

           pair p={size+a-1, size+b-1};

           int flag=0;
           while(p.first<=p.second){
                if(p.first%2==1){
                    nodes[p.first]+=1;
                    p.first+=1;
                }

                if(p.second%2==0){
                    nodes[p.second]+=1;
                    p.second-=1;
                }

                p.first/=2;
                p.second/=2;
           }


        }

        else if(c=='Q'){
            int v, chunk;
            cin>>v>>chunk;
            if(graph[v].first<=chunk && graph[v].second>=chunk){
                cout<<"yes"<<"\n";
            }
            else cout<<"no"<<"\n";
        }

        else{
            int chunk; cin>>chunk;

            chunk+=size-1;  
            int ans=0;
            while(chunk>0){
                ans+=nodes[chunk];
                chunk/=2;
            }

            cout<<ans<<"\n";

        }

        // for(int i=1; i<=n; i++){
        //     cout<<graph[i].first<<" "<<graph[i].second<<"\n";
        // }
        // cout<<"\n";
    }

    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:65:16: warning: unused variable 'flag' [-Wunused-variable]
   65 |            int flag=0;
      |                ^~~~

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