oj.uz

Submission #477758

# Submission time Handle Problem Language Result Execution time Memory
477758 2021-10-03T11:44:00 Z pypcdev Game (IOI13_game) C++17
36 / 100
 3084 ms 256004 KB 
#include<bits/stdc++.h>
#include"game.h"
using namespace std;
const 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;
        if(y2<=m){
            v->try_create(v->left);
            return get(v->left,l,m,y1,y2);
        }else if(y1>m){
            v->try_create(v->right);
            return get(v->right,m+1,r,y1,y2);
        }else{
            v->try_create(v->left);
            v->try_create(v->right);
            return merge(get(v->left,l,m,y1,m),get(v->right,m+1,r,m+1,y2));
        }
    }
    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;
        v->try_create(v->left);
        v->try_create(v->right);
        if(pos<=m){
            upd(v->left,l,m,pos,val);
        }else{
            upd(v->right,m+1,r,pos,val);
        }
        v->val=merge(v->left->val,v->right->val);
    }
};
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);
        }
        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){
}
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
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 1076 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1549 ms 138564 KB Output is correct
5 Correct 1033 ms 121808 KB Output is correct
6 Runtime error 1909 ms 256004 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 1100 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1059 ms 33828 KB Output is correct
13 Correct 1322 ms 16284 KB Output is correct
14 Correct 793 ms 2420 KB Output is correct
15 Correct 1672 ms 26556 KB Output is correct
16 Correct 541 ms 49216 KB Output is correct
17 Correct 2600 ms 180340 KB Output is correct
18 Correct 3084 ms 189900 KB Output is correct
19 Correct 3074 ms 189856 KB Output is correct
20 Correct 2920 ms 189048 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 4 ms 1100 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1483 ms 138800 KB Output is correct
13 Correct 1041 ms 121900 KB Output is correct
14 Runtime error 1863 ms 256004 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 3 ms 1100 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 2 ms 784 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1432 ms 138920 KB Output is correct
13 Correct 1077 ms 121912 KB Output is correct
14 Runtime error 1807 ms 256004 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -