oj.uz

Submission #12945

# Submission time Handle Problem Language Result Execution time Memory
12945 2015-01-21T08:34:25 Z gs14004 Game (IOI13_game) C++
100 / 100
 11852 ms 110240 KB 
#include "game.h"
#include <cstdlib>

int r,c;
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 nodey{
    nodey() : ls(NULL), rs(NULL), v(0ll), pos(0){}
    nodey *ls,*rs;
    long long v;
    int pos;
};
struct nodex{
    nodex() : ls(NULL), rs(NULL), ys(){}
    nodex *ls,*rs;
    nodey *ys;
}*root;

void Yadd(int y, int ps, int pe, nodey* p, long long v){
    if(!p->ls && !p->rs && !p->pos){
        p->pos = y+1;
        p->v = v;
        return;
    }
    if(p -> pos){
        if(p -> pos == y+1){
            p->v = v;
            return;
        }
        else{
            int t = p -> pos - 1;
            long long u = p->v;
            p -> pos = 0;
            p->v = 0;
            p->ls = new nodey();
            p->rs = new nodey();
            Yadd(t,ps,pe,p,u);
        }
    }
    int pm = (ps+pe)/2;
    if(y <= pm){
        if(!p->ls) p->ls = new nodey();
        Yadd(y,ps,pm,p->ls,v);
        p->v = gcd2(p->ls->v,(p->rs ? p->rs->v : 0));
    }
    else{
        if(!p->rs) p->rs = new nodey();
        Yadd(y,pm+1,pe,p->rs,v);
        p->v = gcd2(p->rs->v,(p->ls ? p->ls->v : 0));
    }
}

long long Yquery(int s, int e, int ps, int pe, nodey* p){
    if(pe < s || e < ps) return 0;
    if(p -> pos){
        if(s <= (p->pos) - 1 && (p->pos)-1 <= e){
            return p->v;
        }
        else return 0;
    }
    if(s <= ps && pe <= e){
        return p->v;
    }
    long long r = 0;
    int pm = (ps+pe)/2;
    if(p->ls) r = gcd2(r,Yquery(s,e,ps,pm,p->ls));
    if(p->rs) r = gcd2(r,Yquery(s,e,pm+1,pe,p->rs));
    return r;
}

void Xadd(int x, int y, int ps, int pe, nodex *p, long long v){
    if(ps == pe){
        if(!p->ys) p->ys = new nodey();
        Yadd(y,0,c-1,p->ys,v);
        return;
    }
    int pm = (ps+pe)/2;
    if(x <= pm){
        if(!p->ls) p->ls = new nodex();
        Xadd(x,y,ps,pm,p->ls,v);
        long long val = Yquery(y,y,0,c-1,p->ls->ys);
        if(p->rs) val = gcd2(val,Yquery(y,y,0,c-1,p->rs->ys));
        if(!p->ys) p->ys = new nodey();
        Yadd(y,0,c-1,p->ys,val);
    }
    else{
        if(!p->rs) p->rs = new nodex();
        Xadd(x,y,pm+1,pe,p->rs,v);
        long long val = Yquery(y,y,0,c-1,p->rs->ys);
        if(p->ls) val = gcd2(val,Yquery(y,y,0,c-1,p->ls->ys));
        if(!p->ys) p->ys = new nodey();
        Yadd(y,0,c-1,p->ys,val);
    }
}

long long Xquery(int s, int e, int ps, int pe, int sy, int ey, nodex *p){
    if(e < ps || pe < s) return 0;
    if(s <= ps && pe <= e){
        if(!p->ys) return 0;
        return Yquery(sy,ey,0,c-1,p->ys);
    }
    int pm = (ps+pe)/2;
    long long r = 0;
    if(p->ls) r = gcd2(Xquery(s,e,ps,pm,sy,ey,p->ls),r);
    if(p->rs) r = gcd2(Xquery(s,e,pm+1,pe,sy,ey,p->rs),r);
    return r;
}

void init(int R, int C) {
    root = new nodex();
    r = R, c = C;
}

void update(int P, int Q, long long K) {
    Xadd(P,Q,0,r-1,root,K);
}

long long calculate(int P, int Q, int U, int V) {
    return Xquery(P,U,0,r-1,Q,V,root);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 0 ms 1208 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 828 ms 6620 KB Output is correct
5 Correct 544 ms 6620 KB Output is correct
6 Correct 744 ms 6752 KB Output is correct
7 Correct 840 ms 6752 KB Output is correct
8 Correct 528 ms 3848 KB Output is correct
9 Correct 796 ms 6620 KB Output is correct
10 Correct 692 ms 6752 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 1324 ms 10184 KB Output is correct
13 Correct 3100 ms 6752 KB Output is correct
14 Correct 480 ms 1340 KB Output is correct
15 Correct 3684 ms 8864 KB Output is correct
16 Correct 292 ms 12692 KB Output is correct
17 Correct 1228 ms 7148 KB Output is correct
18 Correct 2092 ms 12692 KB Output is correct
19 Correct 1788 ms 12692 KB Output is correct
20 Correct 1608 ms 12692 KB Output is correct
21 Correct 0 ms 1208 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 828 ms 6620 KB Output is correct
13 Correct 504 ms 6620 KB Output is correct
14 Correct 752 ms 6752 KB Output is correct
15 Correct 824 ms 6752 KB Output is correct
16 Correct 512 ms 3848 KB Output is correct
17 Correct 788 ms 6620 KB Output is correct
18 Correct 704 ms 6752 KB Output is correct
19 Correct 1352 ms 10184 KB Output is correct
20 Correct 3096 ms 6752 KB Output is correct
21 Correct 468 ms 1340 KB Output is correct
22 Correct 3668 ms 8864 KB Output is correct
23 Correct 312 ms 12692 KB Output is correct
24 Correct 1216 ms 7148 KB Output is correct
25 Correct 2020 ms 12692 KB Output is correct
26 Correct 1748 ms 12692 KB Output is correct
27 Correct 1608 ms 12692 KB Output is correct
28 Correct 820 ms 48464 KB Output is correct
29 Correct 1968 ms 33548 KB Output is correct
30 Correct 9420 ms 47804 KB Output is correct
31 Correct 8884 ms 35924 KB Output is correct
32 Correct 1068 ms 2132 KB Output is correct
33 Correct 1352 ms 8600 KB Output is correct
34 Correct 404 ms 33416 KB Output is correct
35 Correct 1472 ms 16784 KB Output is correct
36 Correct 2704 ms 33416 KB Output is correct
37 Correct 2184 ms 33548 KB Output is correct
38 Correct 2068 ms 33548 KB Output is correct
39 Correct 1892 ms 25628 KB Output is correct
40 Correct 0 ms 1208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 820 ms 6620 KB Output is correct
13 Correct 548 ms 6620 KB Output is correct
14 Correct 728 ms 6752 KB Output is correct
15 Correct 836 ms 6752 KB Output is correct
16 Correct 524 ms 3848 KB Output is correct
17 Correct 800 ms 6620 KB Output is correct
18 Correct 680 ms 6752 KB Output is correct
19 Correct 1308 ms 10184 KB Output is correct
20 Correct 3112 ms 6752 KB Output is correct
21 Correct 468 ms 1340 KB Output is correct
22 Correct 3632 ms 8864 KB Output is correct
23 Correct 304 ms 12692 KB Output is correct
24 Correct 1196 ms 7148 KB Output is correct
25 Correct 2200 ms 12692 KB Output is correct
26 Correct 1780 ms 12692 KB Output is correct
27 Correct 1576 ms 12692 KB Output is correct
28 Correct 820 ms 48464 KB Output is correct
29 Correct 1952 ms 33548 KB Output is correct
30 Correct 9376 ms 47804 KB Output is correct
31 Correct 8820 ms 35924 KB Output is correct
32 Correct 1068 ms 2132 KB Output is correct
33 Correct 1324 ms 8600 KB Output is correct
34 Correct 384 ms 33416 KB Output is correct
35 Correct 1548 ms 16784 KB Output is correct
36 Correct 2688 ms 33416 KB Output is correct
37 Correct 2148 ms 33548 KB Output is correct
38 Correct 2124 ms 33548 KB Output is correct
39 Correct 1192 ms 110240 KB Output is correct
40 Correct 2968 ms 73544 KB Output is correct
41 Correct 11852 ms 103112 KB Output is correct
42 Correct 11352 ms 77504 KB Output is correct
43 Correct 740 ms 73676 KB Output is correct
44 Correct 1636 ms 2000 KB Output is correct
45 Correct 1876 ms 25628 KB Output is correct
46 Correct 3396 ms 73676 KB Output is correct
47 Correct 3416 ms 73808 KB Output is correct
48 Correct 3320 ms 73676 KB Output is correct
49 Correct 0 ms 1208 KB Output is correct