Submission #1101344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101344		alexander707070	Game (IOI13_game)	C++14	0 / 100	3 ms	952 KiB

game

#include<bits/stdc++.h>
#include "game.h"

#define MAXN 500007
using namespace std;

const long long maxs=1e9;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct ST2D{

    struct ST{
        
        struct node{
            long long l,r;
            long long val;
        };

        vector<node> tree;
        long long num;

        void init(){
            tree.push_back({0,0,0});
            tree.push_back({0,0,0});
            num=1;
        }

        void addnode(){
            num++; tree.push_back({0,0,0});
        }
        
        void check(long long v){
            if(tree[v].l==0){
                addnode(); tree[v].l=num;
            }
            if(tree[v].r==0){
                addnode(); tree[v].r=num;
            }
        }

        void update(long long v,long long l,long long r,long long pos,long long val){
            if(l==r){
                tree[v].val=val;
            }else{
                long long tt=(l+r)/2;
                check(v);

                if(pos<=tt)update(tree[v].l,l,tt,pos,val);
                else update(tree[v].r,tt+1,r,pos,val);

                tree[v].val=gcd2(tree[tree[v].l].val,tree[tree[v].r].val);
            }
        }

        long long getgcd(long long v,long long l,long long r,long long ll,long long rr){
            if(v==0 or ll>rr)return 0;
            if(l==ll and r==rr){
                return tree[v].val;
            }else{
                long long tt=(l+r)/2;
                return gcd2( getgcd(tree[v].l,l,tt,ll,min(tt,rr)) , getgcd(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
            }
        }

        void upd(long long pos,long long val){
            update(1,1,maxs,pos,val);
        }

        long long query(long long l,long long r){
            return getgcd(1,1,maxs,l,r);
        }
    };

    struct node{
        long long l,r;
        ST t;
    };

    vector<node> tree;
    long long num;

    void init(){
        ST a,b;
        a.init(); b.init();
        tree.push_back({0,0,a});
        tree.push_back({0,0,b});
        num=1;
    }

    void addnode(){ 
        ST a; a.init();
        tree.push_back({0,0,a}); 
        num++;
    }
    
    void check(long long v){
        if(tree[v].l==0){
            addnode(); tree[v].l=num;
        }
        if(tree[v].r==0){
            addnode(); tree[v].r=num;
        }
    }

    void update(long long v,long long l,long long r,long long posx,long long posy,long long val){
        if(l==r){
            tree[v].t.upd(posy,val);
        }else{
            long long tt=(l+r)/2;
            check(v);

            if(posx<=tt)update(tree[v].l,l,tt,posx,posy,val);
            else update(tree[v].r,tt+1,r,posx,posy,val);
            
            tree[v].t.upd(posy,val);
        }
    }

    long long getgcd(long long v,long long l,long long r,long long lx,long long rx,long long ly,long long ry){
        if(v==0 or lx>rx)return 0;

        if(l==lx and r==rx){
            return tree[v].t.query(ly,ry);
        }else{
            long long tt=(l+r)/2;
            return gcd2( getgcd(tree[v].l,l,tt,lx,min(tt,rx),ly,ry) , getgcd(tree[v].r,tt+1,r,max(tt+1,lx),rx,ly,ry) );
        }
    }

    void upd(long long x,long long y,long long val){
        update(1,1,maxs,x,y,val);
    }

    long long query(long long a,long long b,long long c,long long d){
        return getgcd(1,1,maxs,a,c,b,d);
    }
}seg;

void init(int R, int C) {
    seg.init();
}

void update(int P, int Q, long long K) {
    P++; Q++;
    seg.upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    P++; Q++; U++; V++;
    return seg.query(P,Q,U,V);
}

/*int main(){

    init(10,10);

    update(0,0,20);
    update(0,2,15);
    update(1,1,12);

    cout<<calculate(0,0,0,2)<<"\n";
    cout<<calculate(0,0,1,1)<<"\n";
    
    update(0,1,6);
    update(1,1,14);

    cout<<calculate(0,0,0,2)<<"\n";
    cout<<calculate(0,0,1,1)<<"\n";

	return 0;
}*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20