oj.uz

Submission #12944

# Submission time Handle Problem Language Result Execution time Memory
12944 2015-01-21T07:51:59 Z gs14004 Game (IOI13_game) C++
63 / 100
 3612 ms 256000 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){}
    nodey *ls,*rs;
    long long v;
};
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(ps == pe){
        p->v = v;
        return;
    }
    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(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 892 ms 9392 KB Output is correct
5 Correct 560 ms 9392 KB Output is correct
6 Correct 788 ms 9656 KB Output is correct
7 Correct 900 ms 9656 KB Output is correct
8 Correct 564 ms 5960 KB Output is correct
9 Correct 900 ms 9656 KB Output is correct
10 Correct 744 ms 9656 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 1396 ms 12560 KB Output is correct
13 Correct 3052 ms 6224 KB Output is correct
14 Correct 432 ms 1208 KB Output is correct
15 Correct 3612 ms 8864 KB Output is correct
16 Correct 316 ms 18368 KB Output is correct
17 Correct 1392 ms 10976 KB Output is correct
18 Correct 2292 ms 18368 KB Output is correct
19 Correct 2004 ms 18368 KB Output is correct
20 Correct 1800 ms 18368 KB Output is correct
21 Correct 0 ms 1208 KB Output is correct

Subtask #4
0.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 892 ms 9392 KB Output is correct
13 Correct 564 ms 9392 KB Output is correct
14 Correct 796 ms 9656 KB Output is correct
15 Correct 920 ms 9656 KB Output is correct
16 Correct 572 ms 5960 KB Output is correct
17 Correct 856 ms 9656 KB Output is correct
18 Correct 760 ms 9656 KB Output is correct
19 Correct 1368 ms 12560 KB Output is correct
20 Correct 3128 ms 6224 KB Output is correct
21 Correct 432 ms 1208 KB Output is correct
22 Correct 3572 ms 8864 KB Output is correct
23 Correct 312 ms 18368 KB Output is correct
24 Correct 1396 ms 10976 KB Output is correct
25 Correct 2312 ms 18368 KB Output is correct
26 Correct 2000 ms 18368 KB Output is correct
27 Correct 1776 ms 18368 KB Output is correct
28 Correct 1364 ms 251348 KB Output is correct
29 Memory limit exceeded 2708 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0.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 876 ms 9392 KB Output is correct
13 Correct 536 ms 9392 KB Output is correct
14 Correct 768 ms 9656 KB Output is correct
15 Correct 920 ms 9656 KB Output is correct
16 Correct 560 ms 5960 KB Output is correct
17 Correct 904 ms 9656 KB Output is correct
18 Correct 748 ms 9656 KB Output is correct
19 Correct 1376 ms 12560 KB Output is correct
20 Correct 3076 ms 6224 KB Output is correct
21 Correct 420 ms 1208 KB Output is correct
22 Correct 3608 ms 8864 KB Output is correct
23 Correct 348 ms 18368 KB Output is correct
24 Correct 1392 ms 10976 KB Output is correct
25 Correct 2260 ms 18368 KB Output is correct
26 Correct 1932 ms 18368 KB Output is correct
27 Correct 1784 ms 18368 KB Output is correct
28 Correct 1304 ms 251348 KB Output is correct
29 Memory limit exceeded 2656 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -