Submission #412118

#	Time	Username	Problem	Language	Result	Execution time	Memory
412118		pliam	Game (IOI13_game)	C++14	63 / 100	1697 ms	256004 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int rows,cols;

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 ny{//node of sty
    int starty,endy,ly,ry,pary;
    ll ans;
    ny(int s,int e,int p){
        starty=s;
        endy=e;
        ly=ry=-1;
        ans=0;
        pary=p;
    }
};

struct sty{
    vector<ny> st;
    int startx,endx,lx,rx,parx;

    sty(int s,int e,int p){
        startx=s;
        endx=e;
        lx=rx=-1;
        parx=p;
        st.push_back(ny(0,cols-1,-1));
    }

    void make_l(int curry){
        int midy=(st[curry].starty+st[curry].endy)/2;
        if(st[curry].ly==-1){
            st[curry].ly=st.size();
            st.push_back(ny(st[curry].starty,midy,curry));
        }
    }

    void make_r(int curry){
        int midy=(st[curry].starty+st[curry].endy)/2;
        if(st[curry].ry==-1){
            st[curry].ry=st.size();
            st.push_back(ny(midy+1,st[curry].endy,curry));
        }
    }

    void updatey(int posy,ll val){
        int curry=0;
        while(st[curry].starty!=st[curry].endy){
            int midy=(st[curry].starty+st[curry].endy)/2;
            if(posy<=midy){
                make_l(curry);
                curry=st[curry].ly;
            }else{
                make_r(curry);
                curry=st[curry].ry;
            }
        }
        st[curry].ans=val;
        returny(curry);
    }

    ll node_ans(int posy){
        int curry=0;
        while((curry!=-1)&&st[curry].starty!=st[curry].endy){
            int midy=(st[curry].starty+st[curry].endy)/2;
            if(posy<=midy){
                curry=st[curry].ly;
            }else{
                curry=st[curry].ry;
            }
        }
        return (curry==-1)?0:st[curry].ans;
    }

    void returny(int curry){
        while(st[curry].pary!=-1){
            curry=st[curry].pary;
            st[curry].ans=gcd2(((st[curry].ly>=0)?st[st[curry].ly].ans:0),((st[curry].ry>=0)?st[st[curry].ry].ans:0));//update
        }
    }

    ll queryy(int fromy,int toy,int curry=0){
        if(curry==-1) return 0;
        if(st[curry].starty==fromy&&st[curry].endy==toy){
            return st[curry].ans;
        }
        int midy=(st[curry].starty+st[curry].endy)/2;
        if(toy<=midy){
            return queryy(fromy,toy,st[curry].ly);
        }else if(fromy>midy){
            return queryy(fromy,toy,st[curry].ry);
        }else{
            return gcd2(queryy(fromy,midy,st[curry].ly),queryy(midy+1,toy,st[curry].ry));
        }
    }
};

struct stx{
    vector<sty> st;

    stx(){
        st.push_back(sty(0,rows-1,-1));
    }

    void make_l(int currx){
        int midx=(st[currx].startx+st[currx].endx)/2;
        if(st[currx].lx==-1){
            st[currx].lx=st.size();
            st.push_back(sty(st[currx].startx,midx,currx));
        }
    }

    void make_r(int currx){
        int midx=(st[currx].startx+st[currx].endx)/2;
        if(st[currx].rx==-1){
            st[currx].rx=st.size();
            st.push_back(sty(midx+1,st[currx].endx,currx));
        }
    }

    void updatex(int posx,int posy,ll val){
        int currx=0;
        while(st[currx].startx!=st[currx].endx){
            int midx=(st[currx].startx+st[currx].endx)/2;
            if(posx<=midx){
                make_l(currx);
                currx=st[currx].lx;
            }else{
                make_r(currx);
                currx=st[currx].rx;
            }
        }
        st[currx].updatey(posy,val);
        returnx(currx,posy);
    }

    void returnx(int currx,int posy){
        while(st[currx].parx!=-1){
            currx=st[currx].parx;
            ll l=(st[currx].lx>=0)?st[st[currx].lx].node_ans(posy):0;
            ll r=(st[currx].rx>=0)?st[st[currx].rx].node_ans(posy):0;
            st[currx].updatey(posy,gcd2(l,r));
        }
    }

    ll queryx(int fromx,int tox,int fromy,int toy,int currx=0){
        if(currx==-1) return 0;
        if(st[currx].startx==fromx&&st[currx].endx==tox){
            return st[currx].queryy(fromy,toy);
        }
        int midx=(st[currx].startx+st[currx].endx)/2;
        if(tox<=midx){
            return queryx(fromx,tox,fromy,toy,st[currx].lx);
        }else if(fromx>midx){
            return queryx(fromx,tox,fromy,toy,st[currx].rx);
        }else{
            return gcd2(queryx(fromx,midx,fromy,toy,st[currx].lx),queryx(midx+1,tox,fromy,toy,st[currx].rx));
        }
    }
};

stx gcd_st;

void init(int R, int C) {
    rows=R;
    cols=C;
    gcd_st=stx();
}

void update(int P, int Q, long long K) {
    gcd_st.updatex(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return gcd_st.queryx(P,U,Q,V);
}

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