oj.uz

Submission #411981

# Submission time Handle Problem Language Result Execution time Memory
411981 2021-05-26T11:34:57 Z pliam Game (IOI13_game) C++14
0 / 100
 1 ms 288 KB 
#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_children(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));
        }
        if(st[curry].ry==-1){
            st[curry].ry=st.size();
            st.push_back(ny(midy+1,st[curry].endy,curry));
        }
    }

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

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

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

    ll queryy(int fromy,int toy,int curry=0){
        if(st[curry].starty==fromy&&st[curry].endy==toy){
            return st[curry].ans;
        }
        make_children(curry);
        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_children(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));
        }
        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;
            make_children(currx);
            if(posx<=midx){
                currx=st[currx].lx;
            }else{
                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[st[currx].lx].node_ans(posy);
            ll r=st[st[currx].rx].node_ans(posy);
            st[currx].updatey(posy,gcd2(l,r));
        }
    }

    ll queryx(int fromx,int tox,int fromy,int toy,int currx=0){
        if(st[currx].startx==fromx&&st[currx].endx==tox){
            return st[currx].queryy(fromy,toy);
        }
        make_children(currx);
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -