oj.uz

Submission #477763

# Submission time Handle Problem Language Result Execution time Memory
477763 2021-10-03T11:57:05 Z pypcdev Game (IOI13_game) C++14
63 / 100
 2692 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;
        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);
        }
        //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
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1146 ms 86204 KB Output is correct
5 Correct 786 ms 75204 KB Output is correct
6 Correct 1661 ms 172004 KB Output is correct
7 Correct 1736 ms 171808 KB Output is correct
8 Correct 1428 ms 168904 KB Output is correct
9 Correct 1642 ms 175700 KB Output is correct
10 Correct 1585 ms 171572 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 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 933 ms 28100 KB Output is correct
13 Correct 1320 ms 10664 KB Output is correct
14 Correct 655 ms 1996 KB Output is correct
15 Correct 1651 ms 16532 KB Output is correct
16 Correct 725 ms 38852 KB Output is correct
17 Correct 2524 ms 168400 KB Output is correct
18 Correct 2692 ms 177444 KB Output is correct
19 Correct 2463 ms 177232 KB Output is correct
20 Correct 2375 ms 176640 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 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1075 ms 86100 KB Output is correct
13 Correct 808 ms 75284 KB Output is correct
14 Correct 1616 ms 172040 KB Output is correct
15 Correct 1792 ms 171924 KB Output is correct
16 Correct 1360 ms 168896 KB Output is correct
17 Correct 1624 ms 175956 KB Output is correct
18 Correct 1587 ms 171724 KB Output is correct
19 Correct 918 ms 28144 KB Output is correct
20 Correct 1319 ms 10660 KB Output is correct
21 Correct 640 ms 2116 KB Output is correct
22 Correct 1645 ms 16512 KB Output is correct
23 Correct 733 ms 38740 KB Output is correct
24 Correct 2213 ms 168516 KB Output is correct
25 Correct 2497 ms 177532 KB Output is correct
26 Correct 2454 ms 177092 KB Output is correct
27 Correct 2385 ms 176652 KB Output is correct
28 Runtime error 374 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 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1058 ms 86172 KB Output is correct
13 Correct 773 ms 75204 KB Output is correct
14 Correct 1611 ms 172100 KB Output is correct
15 Correct 1708 ms 171736 KB Output is correct
16 Correct 1390 ms 168892 KB Output is correct
17 Correct 1661 ms 175692 KB Output is correct
18 Correct 1656 ms 171504 KB Output is correct
19 Correct 924 ms 28228 KB Output is correct
20 Correct 1309 ms 10692 KB Output is correct
21 Correct 667 ms 1988 KB Output is correct
22 Correct 1620 ms 16620 KB Output is correct
23 Correct 702 ms 38852 KB Output is correct
24 Correct 2170 ms 168424 KB Output is correct
25 Correct 2588 ms 177388 KB Output is correct
26 Correct 2629 ms 177148 KB Output is correct
27 Correct 2466 ms 176528 KB Output is correct
28 Runtime error 385 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -