oj.uz

Submission #899287

# Submission time Handle Problem Language Result Execution time Memory
899287 2024-01-05T16:53:34 Z AIF_is_carving Inside information (BOI21_servers) C++17
10 / 100
 52 ms 9808 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6736 KB Output is correct
2 Correct 52 ms 8928 KB Output is correct
3 Correct 48 ms 8784 KB Output is correct
4 Correct 50 ms 8976 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6736 KB Output is correct
2 Correct 52 ms 8928 KB Output is correct
3 Correct 48 ms 8784 KB Output is correct
4 Correct 50 ms 8976 KB Output is correct
5 Correct 19 ms 6728 KB Output is correct
6 Correct 50 ms 8712 KB Output is correct
7 Correct 50 ms 9808 KB Output is correct
8 Correct 44 ms 9348 KB Output is correct
9 Correct 40 ms 9316 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6740 KB Output is correct
2 Correct 51 ms 8788 KB Output is correct
3 Correct 45 ms 8788 KB Output is correct
4 Correct 50 ms 8788 KB Output is correct
5 Incorrect 19 ms 6492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6740 KB Output is correct
2 Correct 51 ms 8788 KB Output is correct
3 Correct 45 ms 8788 KB Output is correct
4 Correct 50 ms 8788 KB Output is correct
5 Incorrect 19 ms 6492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6508 KB Output isn't correct
2 Halted 0 ms 0 KB -