oj.uz

Submission #477792

# Submission time Handle Problem Language Result Execution time Memory
477792 2021-10-03T17:46:24 Z pypcdev Game (IOI13_game) C++17
63 / 100
 1478 ms 256004 KB 
#include<bits/stdc++.h>
#include"game.h"
using namespace std;
int MAX=1e9;
struct gcdNode{
    gcdNode*left;gcdNode*right;
    long long val;
    gcdNode(){
        val=0;
        left=NULL;
        right=NULL;
    }
    void try_create(gcdNode*&root){
        if(root==NULL)root=new gcdNode();
    }
};
long long gcd(long long left,long long right){
    if(left==0&&right==0)return 0;
    if(left==0||right==0)return left^right;
    return __gcd(left,right);
}
long long merge(long long left,long long right){
    return gcd(left,right);
    //return left+right;
}
struct segTreeNode{
    gcdNode*root;
    segTreeNode*left;segTreeNode*right;
    segTreeNode(){
        root=new gcdNode();
        left=NULL;
        right=NULL;
    }
    void try_create(segTreeNode*&v){
        if(v==NULL)v=new segTreeNode();
    }
    long long get(gcdNode*&v,int l,int r,int y1,int y2){
        if(y1==l&&y2==r){
            return v->val;
        }
        int m=(l+r)/2;
        long long res;
        if(y2<=m){
            if(v->left==NULL)return 0;
            return get(v->left,l,m,y1,y2);
        }else if(y1>m){
            if(v->right==NULL)return 0;
            return get(v->right,m+1,r,y1,y2);
        }else{
            long long r1,r2;
            if(v->left==NULL)r1=0;
            else r1=get(v->left,l,m,y1,m);
            if(v->right==NULL)r2=0;
            else r2=get(v->right,m+1,r,m+1,y2);
            return merge(r1,r2);
        }
    }
    void upd(gcdNode*&v,int l,int r,int pos,long long val){
        if(l==pos&&r==pos){
            v->val=val;
            return;
        }
        int m=(l+r)/2;
        if(pos<=m){
            v->try_create(v->left);
            upd(v->left,l,m,pos,val);
        }else{
            v->try_create(v->right);
            upd(v->right,m+1,r,pos,val);
        }
        long long r1,r2;
        if(v->left==NULL)r1=0;
        else r1=v->left->val;
        if(v->right==NULL)r2=0;
        else r2=v->right->val;
        v->val=merge(r1,r2);
    }
};
struct segTreeNode2{
    segTreeNode*root;
    segTreeNode2(){
        root=new segTreeNode();
    }
    long long get(segTreeNode*&v,int l,int r,int x1,int x2,int y1,int y2){
        if(l==x1&&r==x2){
            return v->get(v->root,0,MAX,y1,y2);
        }
        int m=(l+r)/2;
        if(x2<=m){
            v->try_create(v->left);
            return get(v->left,l,m,x1,x2,y1,y2);
        }else if(x1>m){
            v->try_create(v->right);
            return get(v->right,m+1,r,x1,x2,y1,y2);
        }else{
            v->try_create(v->left);
            v->try_create(v->right);
            return merge(get(v->left,l,m,x1,m,y1,y2),get(v->right,m+1,r,m+1,x2,y1,y2));
        }
    }
    void upd(segTreeNode*&v,int l,int r,int x,int y,long long val){
        if(l==r&&l==x){
            v->upd(v->root,0,MAX,y,val);
            return;
        }
        int m=(l+r)/2;
        v->try_create(v->left);
        v->try_create(v->right);
        if(x<=m){
            upd(v->left,l,m,x,y,val);
        }else{
            upd(v->right,m+1,r,x,y,val);
        }
        //delete &l;
        //delete &r;
        //delete &x;
        //delete &val;
        long long res=merge(v->left->get(v->left->root,0,MAX,y,y),v->right->get(v->right->root,0,MAX,y,y));
        v->upd(v->root,0,MAX,y,res);
    }
};
segTreeNode2 root;

void init(int R,int C){
    MAX=max(R,C);
}
void update(int P,int Q,long long K){
    root.upd(root.root,0,MAX,Q,P,K);
}
long long calculate(int P,int Q,int U,int V){
    return root.get(root.root,0,MAX,Q,V,P,U);
}
/*signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    while(c--){
        int t;
        cin>>t;
        if(t==2){
            int P,Q,U,V;
            cin>>P>>Q>>U>>V;
            cout<<"RES: "<<calculate(P,Q,U,V)<<"\n";
        }else{
            int P,Q;long long val;
            cin>>P>>Q>>val;
            update(P,Q,val);
        }
    }

}*/
/*
2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1
*/

Compilation message

game.cpp: In member function 'long long int segTreeNode::get(gcdNode*&, int, int, int, int)':
game.cpp:42:19: warning: unused variable 'res' [-Wunused-variable]
   42 |         long long res;
      |                   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 764 ms 36104 KB Output is correct
5 Correct 613 ms 35360 KB Output is correct
6 Correct 934 ms 39512 KB Output is correct
7 Correct 1042 ms 39088 KB Output is correct
8 Correct 679 ms 29136 KB Output is correct
9 Correct 1018 ms 39516 KB Output is correct
10 Correct 963 ms 38884 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 679 ms 15768 KB Output is correct
13 Correct 1187 ms 6084 KB Output is correct
14 Correct 261 ms 956 KB Output is correct
15 Correct 1384 ms 8736 KB Output is correct
16 Correct 602 ms 18244 KB Output is correct
17 Correct 631 ms 11472 KB Output is correct
18 Correct 1120 ms 18564 KB Output is correct
19 Correct 952 ms 18604 KB Output is correct
20 Correct 932 ms 18112 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 689 ms 36112 KB Output is correct
13 Correct 594 ms 35316 KB Output is correct
14 Correct 902 ms 39328 KB Output is correct
15 Correct 1000 ms 39272 KB Output is correct
16 Correct 653 ms 29152 KB Output is correct
17 Correct 1025 ms 39612 KB Output is correct
18 Correct 931 ms 38836 KB Output is correct
19 Correct 806 ms 15812 KB Output is correct
20 Correct 1207 ms 6236 KB Output is correct
21 Correct 255 ms 964 KB Output is correct
22 Correct 1386 ms 8896 KB Output is correct
23 Correct 559 ms 18244 KB Output is correct
24 Correct 659 ms 11452 KB Output is correct
25 Correct 1103 ms 18552 KB Output is correct
26 Correct 965 ms 18708 KB Output is correct
27 Correct 905 ms 17988 KB Output is correct
28 Runtime error 587 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 677 ms 36148 KB Output is correct
13 Correct 586 ms 35360 KB Output is correct
14 Correct 968 ms 39552 KB Output is correct
15 Correct 1117 ms 39200 KB Output is correct
16 Correct 708 ms 29244 KB Output is correct
17 Correct 1026 ms 39700 KB Output is correct
18 Correct 936 ms 38836 KB Output is correct
19 Correct 730 ms 15756 KB Output is correct
20 Correct 1183 ms 6084 KB Output is correct
21 Correct 277 ms 920 KB Output is correct
22 Correct 1478 ms 8768 KB Output is correct
23 Correct 580 ms 18656 KB Output is correct
24 Correct 642 ms 11504 KB Output is correct
25 Correct 1152 ms 18632 KB Output is correct
26 Correct 977 ms 18704 KB Output is correct
27 Correct 867 ms 18056 KB Output is correct
28 Runtime error 560 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -