Submission #477760

#	Time	Username	Problem	Language	Result	Execution time	Memory
477760		pypcdev	Game (IOI13_game)	C++11	63 / 100	2549 ms	256004 KiB

game

#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);
        }
        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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20