oj.uz

Submission #31434

# Submission time Handle Problem Language Result Execution time Memory
31434 2017-08-25T13:07:09 Z gs14004 Game (IOI13_game) C++14
100 / 100
 6493 ms 110336 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(r == 1) return r;
    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(r == 1) return 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);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 856 ms 6716 KB Output is correct
5 Correct 543 ms 6584 KB Output is correct
6 Correct 849 ms 6716 KB Output is correct
7 Correct 1029 ms 6716 KB Output is correct
8 Correct 563 ms 3944 KB Output is correct
9 Correct 826 ms 6716 KB Output is correct
10 Correct 453 ms 6716 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1304 KB Output is correct
3 Correct 0 ms 1304 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1304 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1304 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct
12 Correct 1259 ms 10148 KB Output is correct
13 Correct 2919 ms 6716 KB Output is correct
14 Correct 349 ms 1436 KB Output is correct
15 Correct 3206 ms 8960 KB Output is correct
16 Correct 359 ms 12656 KB Output is correct
17 Correct 1503 ms 7244 KB Output is correct
18 Correct 2019 ms 12788 KB Output is correct
19 Correct 2286 ms 12656 KB Output is correct
20 Correct 659 ms 12788 KB Output is correct
21 Correct 0 ms 1172 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1304 KB Output is correct
3 Correct 0 ms 1304 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1304 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1304 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct
12 Correct 853 ms 6716 KB Output is correct
13 Correct 583 ms 6584 KB Output is correct
14 Correct 786 ms 6716 KB Output is correct
15 Correct 923 ms 6716 KB Output is correct
16 Correct 523 ms 3944 KB Output is correct
17 Correct 829 ms 6716 KB Output is correct
18 Correct 499 ms 6716 KB Output is correct
19 Correct 1239 ms 10148 KB Output is correct
20 Correct 2776 ms 6716 KB Output is correct
21 Correct 333 ms 1436 KB Output is correct
22 Correct 3066 ms 8960 KB Output is correct
23 Correct 279 ms 12656 KB Output is correct
24 Correct 1293 ms 7244 KB Output is correct
25 Correct 2146 ms 12788 KB Output is correct
26 Correct 2339 ms 12656 KB Output is correct
27 Correct 696 ms 12788 KB Output is correct
28 Correct 943 ms 48560 KB Output is correct
29 Correct 2283 ms 33512 KB Output is correct
30 Correct 6493 ms 47900 KB Output is correct
31 Correct 6393 ms 36020 KB Output is correct
32 Correct 779 ms 2096 KB Output is correct
33 Correct 869 ms 8696 KB Output is correct
34 Correct 399 ms 33512 KB Output is correct
35 Correct 1469 ms 16748 KB Output is correct
36 Correct 2799 ms 33380 KB Output is correct
37 Correct 2496 ms 33644 KB Output is correct
38 Correct 1106 ms 33644 KB Output is correct
39 Correct 2516 ms 25592 KB Output is correct
40 Correct 0 ms 1172 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1304 KB Output is correct
3 Correct 0 ms 1304 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1304 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1304 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct
12 Correct 896 ms 6716 KB Output is correct
13 Correct 609 ms 6584 KB Output is correct
14 Correct 903 ms 6716 KB Output is correct
15 Correct 903 ms 6716 KB Output is correct
16 Correct 639 ms 3944 KB Output is correct
17 Correct 923 ms 6716 KB Output is correct
18 Correct 516 ms 6716 KB Output is correct
19 Correct 1463 ms 10148 KB Output is correct
20 Correct 2999 ms 6716 KB Output is correct
21 Correct 413 ms 1436 KB Output is correct
22 Correct 3049 ms 8960 KB Output is correct
23 Correct 309 ms 12656 KB Output is correct
24 Correct 1299 ms 7244 KB Output is correct
25 Correct 2123 ms 12788 KB Output is correct
26 Correct 2259 ms 12656 KB Output is correct
27 Correct 793 ms 12788 KB Output is correct
28 Correct 1063 ms 48560 KB Output is correct
29 Correct 1999 ms 33512 KB Output is correct
30 Correct 6063 ms 47900 KB Output is correct
31 Correct 6359 ms 36020 KB Output is correct
32 Correct 919 ms 2096 KB Output is correct
33 Correct 1022 ms 8696 KB Output is correct
34 Correct 453 ms 33512 KB Output is correct
35 Correct 2089 ms 16748 KB Output is correct
36 Correct 3413 ms 33380 KB Output is correct
37 Correct 2513 ms 33644 KB Output is correct
38 Correct 843 ms 33644 KB Output is correct
39 Correct 1576 ms 110336 KB Output is correct
40 Correct 3389 ms 73640 KB Output is correct
41 Correct 3289 ms 103208 KB Output is correct
42 Correct 3976 ms 77600 KB Output is correct
43 Correct 929 ms 73772 KB Output is correct
44 Correct 1309 ms 2096 KB Output is correct
45 Correct 2369 ms 25592 KB Output is correct
46 Correct 4093 ms 73772 KB Output is correct
47 Correct 3609 ms 73772 KB Output is correct
48 Correct 1459 ms 73772 KB Output is correct
49 Correct 0 ms 1172 KB Output is correct