oj.uz

Submission #412004

# Submission time Handle Problem Language Result Execution time Memory
412004 2021-05-26T12:03:52 Z pliam Game (IOI13_game) C++14
37 / 100
 2536 ms 256004 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,ll 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 1 ms 588 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1088 ms 41696 KB Output is correct
5 Correct 681 ms 34272 KB Output is correct
6 Correct 1046 ms 90692 KB Output is correct
7 Correct 1051 ms 91768 KB Output is correct
8 Correct 956 ms 84120 KB Output is correct
9 Correct 1110 ms 91864 KB Output is correct
10 Correct 953 ms 85180 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 800 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 1 ms 280 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 716 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 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1278 ms 46028 KB Output is correct
13 Correct 1653 ms 19388 KB Output is correct
14 Correct 917 ms 6068 KB Output is correct
15 Correct 2099 ms 27852 KB Output is correct
16 Correct 338 ms 66276 KB Output is correct
17 Runtime error 2536 ms 256004 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 2 ms 716 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 716 KB Output is correct
10 Correct 2 ms 544 KB Output is correct
11 Correct 2 ms 288 KB Output is correct
12 Correct 1097 ms 41736 KB Output is correct
13 Correct 653 ms 34304 KB Output is correct
14 Correct 1059 ms 90760 KB Output is correct
15 Correct 1047 ms 91676 KB Output is correct
16 Correct 888 ms 84104 KB Output is correct
17 Correct 1045 ms 91768 KB Output is correct
18 Correct 1010 ms 85232 KB Output is correct
19 Correct 1276 ms 46160 KB Output is correct
20 Correct 1675 ms 19692 KB Output is correct
21 Correct 917 ms 7376 KB Output is correct
22 Correct 2086 ms 28836 KB Output is correct
23 Correct 334 ms 66216 KB Output is correct
24 Runtime error 2493 ms 256004 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 416 KB Output is correct
6 Correct 2 ms 716 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 668 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1084 ms 41884 KB Output is correct
13 Correct 646 ms 34316 KB Output is correct
14 Correct 1030 ms 90708 KB Output is correct
15 Correct 1014 ms 91764 KB Output is correct
16 Correct 905 ms 84184 KB Output is correct
17 Correct 1028 ms 91868 KB Output is correct
18 Correct 962 ms 85380 KB Output is correct
19 Correct 1322 ms 46180 KB Output is correct
20 Correct 1660 ms 19864 KB Output is correct
21 Correct 886 ms 7144 KB Output is correct
22 Correct 2045 ms 28836 KB Output is correct
23 Correct 333 ms 66188 KB Output is correct
24 Runtime error 2445 ms 256004 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -