답안 #13388 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13388	2015-02-15T17:04:39 Z	baneling100	게임 (IOI13_game)	C++	100 / 100	6784 ms	76452 KB

game

#include "game.h"
#include <stdio.h>

struct Xnode {
    Xnode(int l_, int r_) {left=right=NULL, l=l_, r=r_, info=NULL;}
    Xnode *left, *right;
    int l, r;
    long long info;
};
struct Ynode {
    Ynode() {left=right=NULL, Xroot=NULL;}
    Ynode *left, *right;
    Xnode *Xroot;
} *Yroot;
int R, C, P, Q, U, V;
long long K;

long long gcd2(long long X, long long Y) {

    long long tmp;

    if(!X) {
        tmp=X;
        X=Y;
        Y=tmp;
    }
    while(X!=Y && Y!=0) {
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}

void init(int R_, int C_) {

    for(R=1 ; R<R_ ; R<<=1);
    for(C=1 ; C<C_ ; C<<=1);
    Yroot=new Ynode();
}

long long Xcalculate(Xnode *now) {

    long long value=0;

    if(Q<=now->l && now->r<=V) return now->info;
    else {
        if(now->left!=NULL && Q<=now->left->r && now->left->l<=V) value=Xcalculate(now->left);
        if(now->right!=NULL && Q<=now->right->r && now->right->l<=V) value=gcd2(value,Xcalculate(now->right));
        return value;
    }
}

long long Ycalculate(int l, int r, Ynode *now) {

    int m=(l+r)>>1;
    long long value=0;

    if(P<=l && r<=U) {
        if(now->Xroot!=NULL) value=Xcalculate(now->Xroot);
        return value;
    }
    else {
        if(P<=m && now->left!=NULL) value=Ycalculate(l,m,now->left);
        if(m+1<=U && now->right!=NULL) value=gcd2(value,Ycalculate(m+1,r,now->right));
        return value;
    }
}

void Xupdate(Xnode *now) {

    int m=(now->l+now->r)>>1, x, y;
    Xnode *temp;

    if(now->l==Q && Q==now->r) now->info=K;
    else {
        if(Q<=m) {
            if(now->left==NULL) now->left=new Xnode(Q,Q);
            if(Q<now->left->l || now->left->r<Q) {
                temp=now->left;
                now->left=new Xnode(now->l,m);
                if(Q<temp->l) now->left->right=temp;
                else now->left->left=temp;
                while(1) {
                    x=(now->left->r-now->left->l+1)>>1;
                    y=(now->left->l+now->left->r)>>1;
                    if(!(Q&x) && !(temp->l&x)) now->left->r=y;
                    else if(Q&x && temp->l&x) now->left->l=y+1;
                    else break;
                }
            }
            Xupdate(now->left);
        }
        else {
            if(now->right==NULL) now->right=new Xnode(Q,Q);
            if(Q<now->right->l || now->right->r<Q) {
                temp=now->right;
                now->right=new Xnode(m+1,now->r);
                if(Q<temp->l) now->right->right=temp;
                else now->right->left=temp;
                while(1) {
                    x=(now->right->r-now->right->l+1)>>1;
                    y=(now->right->l+now->right->r)>>1;
                    if(!(Q&x) && !(temp->l&x)) now->right->r=y;
                    else if(Q&x && temp->l&x) now->right->l=y+1;
                    else break;
                }
            }
            Xupdate(now->right);
        }
        if(now->right==NULL) now->info=now->left->info;
        else if(now->left==NULL) now->info=now->right->info;
        else now->info=gcd2(now->left->info,now->right->info);
    }
}

void Yupdate(int l, int r, Ynode *now) {

    int m=(l+r)>>1;

    if(l<r) {
        if(P<=m) {
            if(now->left==NULL) now->left=new Ynode();
            Yupdate(l,m,now->left);
        }
        if(m+1<=P) {
            if(now->right==NULL) now->right=new Ynode();
            Yupdate(m+1,r,now->right);
        }
        if(now->right==NULL) K=Xcalculate(now->left->Xroot);
        else if(now->left==NULL) K=Xcalculate(now->right->Xroot);
        else K=gcd2(Xcalculate(now->left->Xroot),Xcalculate(now->right->Xroot));
    }
    if(now->Xroot==NULL) now->Xroot=new Xnode(0,C-1);
    Xupdate(now->Xroot);
}

void update(int P_, int Q_, long long K_) {

    P=P_, Q=Q_, K=K_, V=Q;
    Yupdate(0,R-1,Yroot);
}

long long calculate(int P_, int Q_, int U_, int V_) {

    P=P_, Q=Q_, U=U_, V=V_;
    return Ycalculate(0,R-1,Yroot);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	662 ms	5700 KB	Output is correct
5	Correct	382 ms	5700 KB	Output is correct
6	Correct	681 ms	5700 KB	Output is correct
7	Correct	812 ms	5700 KB	Output is correct
8	Correct	493 ms	3324 KB	Output is correct
9	Correct	776 ms	5700 KB	Output is correct
10	Correct	694 ms	5700 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	1 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1249 ms	8340 KB	Output is correct
13	Correct	2964 ms	5172 KB	Output is correct
14	Correct	304 ms	1212 KB	Output is correct
15	Correct	3333 ms	6360 KB	Output is correct
16	Correct	418 ms	10056 KB	Output is correct
17	Correct	1125 ms	5832 KB	Output is correct
18	Correct	1962 ms	10056 KB	Output is correct
19	Correct	1652 ms	10056 KB	Output is correct
20	Correct	1515 ms	10056 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	1 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	627 ms	5700 KB	Output is correct
13	Correct	405 ms	5700 KB	Output is correct
14	Correct	698 ms	5700 KB	Output is correct
15	Correct	812 ms	5700 KB	Output is correct
16	Correct	486 ms	3324 KB	Output is correct
17	Correct	800 ms	5700 KB	Output is correct
18	Correct	660 ms	5700 KB	Output is correct
19	Correct	1247 ms	8340 KB	Output is correct
20	Correct	2977 ms	5172 KB	Output is correct
21	Correct	303 ms	1212 KB	Output is correct
22	Correct	3334 ms	6360 KB	Output is correct
23	Correct	410 ms	10056 KB	Output is correct
24	Correct	1085 ms	5832 KB	Output is correct
25	Correct	1976 ms	10056 KB	Output is correct
26	Correct	1652 ms	10056 KB	Output is correct
27	Correct	1485 ms	10056 KB	Output is correct
28	Correct	614 ms	35796 KB	Output is correct
29	Correct	1961 ms	35268 KB	Output is correct
30	Correct	4911 ms	30120 KB	Output is correct
31	Correct	4438 ms	22860 KB	Output is correct
32	Correct	424 ms	1344 KB	Output is correct
33	Correct	635 ms	2004 KB	Output is correct
34	Correct	906 ms	35268 KB	Output is correct
35	Correct	1399 ms	18108 KB	Output is correct
36	Correct	2545 ms	35268 KB	Output is correct
37	Correct	2119 ms	35268 KB	Output is correct
38	Correct	2012 ms	35268 KB	Output is correct
39	Correct	1754 ms	27216 KB	Output is correct
40	Correct	0 ms	1212 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	1 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	654 ms	5700 KB	Output is correct
13	Correct	384 ms	5700 KB	Output is correct
14	Correct	711 ms	5700 KB	Output is correct
15	Correct	804 ms	5700 KB	Output is correct
16	Correct	492 ms	3324 KB	Output is correct
17	Correct	813 ms	5700 KB	Output is correct
18	Correct	768 ms	5700 KB	Output is correct
19	Correct	1230 ms	8340 KB	Output is correct
20	Correct	2978 ms	5172 KB	Output is correct
21	Correct	311 ms	1212 KB	Output is correct
22	Correct	3318 ms	6360 KB	Output is correct
23	Correct	412 ms	10056 KB	Output is correct
24	Correct	1089 ms	5832 KB	Output is correct
25	Correct	1950 ms	10056 KB	Output is correct
26	Correct	1620 ms	10056 KB	Output is correct
27	Correct	1443 ms	10056 KB	Output is correct
28	Correct	593 ms	35796 KB	Output is correct
29	Correct	1923 ms	35268 KB	Output is correct
30	Correct	4845 ms	30120 KB	Output is correct
31	Correct	4503 ms	22860 KB	Output is correct
32	Correct	409 ms	1344 KB	Output is correct
33	Correct	632 ms	2004 KB	Output is correct
34	Correct	900 ms	35268 KB	Output is correct
35	Correct	1412 ms	18108 KB	Output is correct
36	Correct	2540 ms	35268 KB	Output is correct
37	Correct	2099 ms	35268 KB	Output is correct
38	Correct	2007 ms	35268 KB	Output is correct
39	Correct	765 ms	76452 KB	Output is correct
40	Correct	3059 ms	75396 KB	Output is correct
41	Correct	6784 ms	63252 KB	Output is correct
42	Correct	6206 ms	47808 KB	Output is correct
43	Correct	1448 ms	75396 KB	Output is correct
44	Correct	548 ms	1476 KB	Output is correct
45	Correct	1766 ms	27216 KB	Output is correct
46	Correct	3283 ms	75528 KB	Output is correct
47	Correct	3336 ms	75396 KB	Output is correct
48	Correct	3107 ms	75396 KB	Output is correct
49	Correct	0 ms	1212 KB	Output is correct

답안 #13388

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