답안 #12946 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12946	2015-01-21T08:45:17 Z	gs14004	게임 (IOI13_game)	C++	100 / 100	10260 ms	84764 KB

game

#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;
            int pm = (ps+pe)/2;
            p->pos = 0;
            p->v = 0;
            if(t <= pm){
                p->ls = new nodey();
                Yadd(t,ps,pm,p->ls,u);
            }
            else{
                p->rs = new nodey();
                Yadd(t,pm+1,pe,p->rs,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

#	결과	메모리	Grader output
1	Correct	1208 KB	Output is correct
2	Correct	1208 KB	Output is correct
3	Correct	1208 KB	Output is correct
4	Correct	1208 KB	Output is correct
5	Correct	1208 KB	Output is correct
6	Correct	1208 KB	Output is correct
7	Correct	1208 KB	Output is correct
8	Correct	1208 KB	Output is correct
9	Correct	1208 KB	Output is correct
10	Correct	1208 KB	Output is correct
11	Correct	1208 KB	Output is correct
12	Correct	1208 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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	820 ms	5828 KB	Output is correct
5	Correct	512 ms	5828 KB	Output is correct
6	Correct	744 ms	5960 KB	Output is correct
7	Correct	816 ms	5960 KB	Output is correct
8	Correct	520 ms	3452 KB	Output is correct
9	Correct	800 ms	5960 KB	Output is correct
10	Correct	684 ms	5960 KB	Output is correct
11	Correct	0 ms	1208 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	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	1308 ms	9260 KB	Output is correct
13	Correct	3120 ms	5960 KB	Output is correct
14	Correct	440 ms	1340 KB	Output is correct
15	Correct	3624 ms	7544 KB	Output is correct
16	Correct	308 ms	11372 KB	Output is correct
17	Correct	1220 ms	6488 KB	Output is correct
18	Correct	2160 ms	11372 KB	Output is correct
19	Correct	1796 ms	11372 KB	Output is correct
20	Correct	1604 ms	11372 KB	Output is correct
21	Correct	0 ms	1208 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	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	836 ms	5828 KB	Output is correct
13	Correct	524 ms	5828 KB	Output is correct
14	Correct	720 ms	5960 KB	Output is correct
15	Correct	844 ms	5960 KB	Output is correct
16	Correct	524 ms	3452 KB	Output is correct
17	Correct	800 ms	5960 KB	Output is correct
18	Correct	684 ms	5960 KB	Output is correct
19	Correct	1308 ms	9260 KB	Output is correct
20	Correct	3144 ms	5960 KB	Output is correct
21	Correct	428 ms	1340 KB	Output is correct
22	Correct	3652 ms	7544 KB	Output is correct
23	Correct	324 ms	11372 KB	Output is correct
24	Correct	1200 ms	6488 KB	Output is correct
25	Correct	2060 ms	11372 KB	Output is correct
26	Correct	1796 ms	11372 KB	Output is correct
27	Correct	1596 ms	11372 KB	Output is correct
28	Correct	788 ms	37904 KB	Output is correct
29	Correct	2020 ms	30380 KB	Output is correct
30	Correct	7732 ms	36716 KB	Output is correct
31	Correct	7324 ms	27740 KB	Output is correct
32	Correct	920 ms	1736 KB	Output is correct
33	Correct	1200 ms	5300 KB	Output is correct
34	Correct	380 ms	30380 KB	Output is correct
35	Correct	1504 ms	15332 KB	Output is correct
36	Correct	2696 ms	30380 KB	Output is correct
37	Correct	2196 ms	30512 KB	Output is correct
38	Correct	2132 ms	30512 KB	Output is correct
39	Correct	1856 ms	23384 KB	Output is correct
40	Correct	0 ms	1208 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	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	808 ms	5828 KB	Output is correct
13	Correct	548 ms	5828 KB	Output is correct
14	Correct	732 ms	5960 KB	Output is correct
15	Correct	820 ms	5960 KB	Output is correct
16	Correct	528 ms	3452 KB	Output is correct
17	Correct	796 ms	5960 KB	Output is correct
18	Correct	720 ms	5960 KB	Output is correct
19	Correct	1324 ms	9260 KB	Output is correct
20	Correct	3128 ms	5960 KB	Output is correct
21	Correct	428 ms	1340 KB	Output is correct
22	Correct	3616 ms	7544 KB	Output is correct
23	Correct	296 ms	11372 KB	Output is correct
24	Correct	1220 ms	6488 KB	Output is correct
25	Correct	2052 ms	11372 KB	Output is correct
26	Correct	1724 ms	11372 KB	Output is correct
27	Correct	1584 ms	11372 KB	Output is correct
28	Correct	736 ms	37904 KB	Output is correct
29	Correct	1996 ms	30380 KB	Output is correct
30	Correct	7864 ms	36716 KB	Output is correct
31	Correct	7320 ms	27740 KB	Output is correct
32	Correct	928 ms	1736 KB	Output is correct
33	Correct	1200 ms	5300 KB	Output is correct
34	Correct	392 ms	30380 KB	Output is correct
35	Correct	1524 ms	15332 KB	Output is correct
36	Correct	2804 ms	30380 KB	Output is correct
37	Correct	2184 ms	30512 KB	Output is correct
38	Correct	2144 ms	30512 KB	Output is correct
39	Correct	1044 ms	84764 KB	Output is correct
40	Correct	3112 ms	66416 KB	Output is correct
41	Correct	10260 ms	78692 KB	Output is correct
42	Correct	9596 ms	59288 KB	Output is correct
43	Correct	720 ms	66416 KB	Output is correct
44	Correct	1384 ms	1736 KB	Output is correct
45	Correct	1908 ms	23384 KB	Output is correct
46	Correct	3564 ms	66416 KB	Output is correct
47	Correct	3416 ms	66548 KB	Output is correct
48	Correct	3236 ms	66416 KB	Output is correct
49	Correct	0 ms	1208 KB	Output is correct

답안 #12946

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0