oj.uz

Submission #477789

# Submission time Handle Problem Language Result Execution time Memory
477789 2021-10-03T17:39:02 Z pypcdev Game (IOI13_game) C++17
63 / 100
 2590 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();
    }
    void try_clear(gcdNode*&root){
        if(root!=NULL&&root->val==0)delete root;
    }
};
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){
            v->try_create(v->left);
            res=get(v->left,l,m,y1,y2);
        }else if(y1>m){
            v->try_create(v->right);
            res=get(v->right,m+1,r,y1,y2);
        }else{
            v->try_create(v->left);
            v->try_create(v->right);
            res=merge(get(v->left,l,m,y1,m),get(v->right,m+1,r,m+1,y2));
        }
        //v->try_clear(v->left);
        //v->try_clear(v->right);
        return res;
    }
    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);
        //v->try_clear(v->left);
        //v->try_clear(v->right);
    }
};
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 1 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 1 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 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 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 1 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 1079 ms 86116 KB Output is correct
5 Correct 791 ms 75264 KB Output is correct
6 Correct 1617 ms 172060 KB Output is correct
7 Correct 1773 ms 171864 KB Output is correct
8 Correct 1503 ms 168884 KB Output is correct
9 Correct 1639 ms 175824 KB Output is correct
10 Correct 1585 ms 171652 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 1 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 1 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 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 1025 ms 28076 KB Output is correct
13 Correct 1382 ms 10596 KB Output is correct
14 Correct 664 ms 2124 KB Output is correct
15 Correct 1665 ms 16656 KB Output is correct
16 Correct 754 ms 38852 KB Output is correct
17 Correct 2226 ms 168476 KB Output is correct
18 Correct 2476 ms 177532 KB Output is correct
19 Correct 2402 ms 177224 KB Output is correct
20 Correct 2380 ms 176604 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 2 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 384 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 1028 ms 86040 KB Output is correct
13 Correct 764 ms 75376 KB Output is correct
14 Correct 1603 ms 172012 KB Output is correct
15 Correct 1738 ms 171780 KB Output is correct
16 Correct 1333 ms 168876 KB Output is correct
17 Correct 1601 ms 175672 KB Output is correct
18 Correct 1514 ms 171524 KB Output is correct
19 Correct 889 ms 28116 KB Output is correct
20 Correct 1332 ms 10604 KB Output is correct
21 Correct 629 ms 2036 KB Output is correct
22 Correct 1634 ms 16536 KB Output is correct
23 Correct 725 ms 38728 KB Output is correct
24 Correct 2203 ms 168400 KB Output is correct
25 Correct 2507 ms 177332 KB Output is correct
26 Correct 2553 ms 177156 KB Output is correct
27 Correct 2371 ms 176648 KB Output is correct
28 Runtime error 375 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 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 1134 ms 86116 KB Output is correct
13 Correct 795 ms 75280 KB Output is correct
14 Correct 1673 ms 172144 KB Output is correct
15 Correct 1697 ms 171764 KB Output is correct
16 Correct 1488 ms 168884 KB Output is correct
17 Correct 1693 ms 175620 KB Output is correct
18 Correct 1604 ms 171488 KB Output is correct
19 Correct 880 ms 28360 KB Output is correct
20 Correct 1336 ms 10832 KB Output is correct
21 Correct 656 ms 2092 KB Output is correct
22 Correct 1622 ms 16708 KB Output is correct
23 Correct 695 ms 38840 KB Output is correct
24 Correct 2074 ms 168336 KB Output is correct
25 Correct 2590 ms 177468 KB Output is correct
26 Correct 2589 ms 177068 KB Output is correct
27 Correct 2351 ms 176744 KB Output is correct
28 Runtime error 375 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -