oj.uz

Submission #412118

# Submission time Handle Problem Language Result Execution time Memory
412118 2021-05-26T14:17:47 Z pliam Game (IOI13_game) C++14
63 / 100
 1697 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_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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 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 204 KB Output is correct
4 Correct 580 ms 19584 KB Output is correct
5 Correct 427 ms 17456 KB Output is correct
6 Correct 482 ms 14944 KB Output is correct
7 Correct 515 ms 14108 KB Output is correct
8 Correct 340 ms 12340 KB Output is correct
9 Correct 502 ms 16688 KB Output is correct
10 Correct 511 ms 15840 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 915 ms 24596 KB Output is correct
13 Correct 1443 ms 10008 KB Output is correct
14 Correct 296 ms 3704 KB Output is correct
15 Correct 1697 ms 13764 KB Output is correct
16 Correct 262 ms 29252 KB Output is correct
17 Correct 756 ms 20432 KB Output is correct
18 Correct 1322 ms 30668 KB Output is correct
19 Correct 1120 ms 30864 KB Output is correct
20 Correct 1059 ms 30048 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 424 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 541 ms 19812 KB Output is correct
13 Correct 422 ms 17460 KB Output is correct
14 Correct 478 ms 14916 KB Output is correct
15 Correct 507 ms 14244 KB Output is correct
16 Correct 346 ms 12296 KB Output is correct
17 Correct 495 ms 16776 KB Output is correct
18 Correct 458 ms 15920 KB Output is correct
19 Correct 910 ms 24632 KB Output is correct
20 Correct 1419 ms 12144 KB Output is correct
21 Correct 298 ms 5696 KB Output is correct
22 Correct 1684 ms 15888 KB Output is correct
23 Correct 251 ms 29252 KB Output is correct
24 Correct 769 ms 20476 KB Output is correct
25 Correct 1275 ms 30752 KB Output is correct
26 Correct 1186 ms 30944 KB Output is correct
27 Correct 1105 ms 30164 KB Output is correct
28 Runtime error 922 ms 256004 KB Execution killed with signal 9
29 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 420 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 284 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 565 ms 19664 KB Output is correct
13 Correct 431 ms 17480 KB Output is correct
14 Correct 489 ms 14924 KB Output is correct
15 Correct 547 ms 14036 KB Output is correct
16 Correct 338 ms 12364 KB Output is correct
17 Correct 507 ms 16700 KB Output is correct
18 Correct 482 ms 15920 KB Output is correct
19 Correct 989 ms 24576 KB Output is correct
20 Correct 1452 ms 11912 KB Output is correct
21 Correct 291 ms 5672 KB Output is correct
22 Correct 1688 ms 15736 KB Output is correct
23 Correct 259 ms 29280 KB Output is correct
24 Correct 759 ms 20344 KB Output is correct
25 Correct 1298 ms 30748 KB Output is correct
26 Correct 1114 ms 30864 KB Output is correct
27 Correct 1046 ms 30348 KB Output is correct
28 Runtime error 851 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -