답안 #13374 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13374	2015-02-14T04:58:11 Z	dohyun0324	게임 (IOI13_game)	C++	63 / 100	3317 ms	256000 KB

game

#include<stdio.h>
#include "game.h"
typedef long long ll;
int n,m,x1,y1,x2,y2;
ll k;
ll gcd2(ll X, ll Y) {
    if(X==0) return Y; if(Y==0) return X;
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct data
{
    data *l,*r;
    data(){l=r=NULL;}
    void update3(int rx,int ry)
    {
        if(rx==ry){start2.update2(1,m); return;}
        int mid=(rx+ry)/2;
        if(x1<=mid)
        {
            if(l==NULL) l=new data();
            l->update3(rx,mid);
        }
        else
        {
            if(r==NULL) r=new data();
            r->update3(mid+1,ry);
        }
        x2=y1; y2=y1;
        if(r==NULL) k=l->start2.query2(1,m);
        else if(l==NULL) k=r->start2.query2(1,m);
        else k=gcd2(l->start2.query2(1,m),r->start2.query2(1,m));
        start2.update2(1,m);
    }
    ll query(int rx,int ry)
    {
        int mid=(rx+ry)/2;
        if(x1<=rx && ry<=y1) return start2.query2(1,m);
        if(x1>ry || y1<rx) return 0;
        if(l==NULL && r==NULL) return 0;
        else if(l==NULL) return r->query(mid+1,ry);
        else if(r==NULL) return l->query(rx,mid);
        return gcd2(l->query(rx,mid),r->query(mid+1,ry));
    }
    struct data2
    {
        ll val;
        data2 *l,*r;
        data2(){}
        data2(ll v):val(v){l=r=NULL;}
        void update2(int cx,int cy)
        {
            if(cx==cy){val=k; return;}
            int mid=(cx+cy)/2;
            if(y1<=mid){
                if(l==NULL) l=new data2(0);
                l->update2(cx,mid);
            }
            else{
                if(r==NULL) r=new data2(0);
                r->update2(mid+1,cy);
            }
            if(r==NULL) val=l->val;
            else if(l==NULL) val=r->val;
            else val=gcd2(l->val,r->val);
        }
        ll query2(int cx,int cy)
        {
            int mid=(cx+cy)/2;
            if(cx>y2 || cy<x2) return 0;
            if((x2<=cx && cy<=y2) || (l==NULL && r==NULL)) return val;
            if(l==NULL) return r->query2(mid+1,cy);
            else if(r==NULL) return l->query2(cx,mid);
            return gcd2(l->query2(cx,mid),r->query2(mid+1,cy));
        }
    };
    data2 start2=data2(0);
};
void init(int R, int C){
    n=R+1, m=C+1;
}
data start=data();
void update(int P, int Q, ll K){
    x1=P+1; y1=Q+1; k=K;
    start.update3(1,n);
}
ll calculate(int P, int Q, int U, int V){
    x1=P+1; y1=U+1; x2=Q+1; y2=V+1;
    return start.query(1,n);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1256 KB	Output is correct
2	Correct	0 ms	1256 KB	Output is correct
3	Correct	0 ms	1256 KB	Output is correct
4	Correct	731 ms	9836 KB	Output is correct
5	Correct	516 ms	9836 KB	Output is correct
6	Correct	762 ms	10100 KB	Output is correct
7	Correct	878 ms	10100 KB	Output is correct
8	Correct	541 ms	6140 KB	Output is correct
9	Correct	840 ms	10100 KB	Output is correct
10	Correct	700 ms	10100 KB	Output is correct
11	Correct	0 ms	1256 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1256 KB	Output is correct
2	Correct	0 ms	1256 KB	Output is correct
3	Correct	0 ms	1256 KB	Output is correct
4	Correct	0 ms	1256 KB	Output is correct
5	Correct	0 ms	1256 KB	Output is correct
6	Correct	0 ms	1256 KB	Output is correct
7	Correct	0 ms	1256 KB	Output is correct
8	Correct	0 ms	1256 KB	Output is correct
9	Correct	0 ms	1256 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	0 ms	1256 KB	Output is correct
12	Correct	1221 ms	12608 KB	Output is correct
13	Correct	2896 ms	6404 KB	Output is correct
14	Correct	358 ms	1388 KB	Output is correct
15	Correct	3259 ms	8912 KB	Output is correct
16	Correct	1057 ms	18284 KB	Output is correct
17	Correct	1299 ms	11024 KB	Output is correct
18	Correct	2060 ms	18284 KB	Output is correct
19	Correct	1824 ms	18284 KB	Output is correct
20	Correct	1666 ms	18284 KB	Output is correct
21	Correct	0 ms	1256 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1256 KB	Output is correct
2	Correct	0 ms	1256 KB	Output is correct
3	Correct	0 ms	1256 KB	Output is correct
4	Correct	0 ms	1256 KB	Output is correct
5	Correct	0 ms	1256 KB	Output is correct
6	Correct	0 ms	1256 KB	Output is correct
7	Correct	0 ms	1256 KB	Output is correct
8	Correct	0 ms	1256 KB	Output is correct
9	Correct	0 ms	1256 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	1 ms	1256 KB	Output is correct
12	Correct	732 ms	9836 KB	Output is correct
13	Correct	516 ms	9836 KB	Output is correct
14	Correct	774 ms	10100 KB	Output is correct
15	Correct	871 ms	10100 KB	Output is correct
16	Correct	561 ms	6140 KB	Output is correct
17	Correct	854 ms	10100 KB	Output is correct
18	Correct	699 ms	10100 KB	Output is correct
19	Correct	1202 ms	12608 KB	Output is correct
20	Correct	2914 ms	6404 KB	Output is correct
21	Correct	359 ms	1388 KB	Output is correct
22	Correct	3317 ms	8912 KB	Output is correct
23	Correct	1089 ms	18284 KB	Output is correct
24	Correct	1299 ms	11024 KB	Output is correct
25	Correct	2087 ms	18284 KB	Output is correct
26	Correct	1794 ms	18284 KB	Output is correct
27	Correct	1586 ms	18284 KB	Output is correct
28	Correct	1087 ms	248624 KB	Output is correct
29	Memory limit exceeded	2311 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1256 KB	Output is correct
2	Correct	0 ms	1256 KB	Output is correct
3	Correct	0 ms	1256 KB	Output is correct
4	Correct	0 ms	1256 KB	Output is correct
5	Correct	0 ms	1256 KB	Output is correct
6	Correct	0 ms	1256 KB	Output is correct
7	Correct	0 ms	1256 KB	Output is correct
8	Correct	0 ms	1256 KB	Output is correct
9	Correct	0 ms	1256 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	0 ms	1256 KB	Output is correct
12	Correct	716 ms	9836 KB	Output is correct
13	Correct	521 ms	9836 KB	Output is correct
14	Correct	778 ms	10100 KB	Output is correct
15	Correct	853 ms	10100 KB	Output is correct
16	Correct	579 ms	6140 KB	Output is correct
17	Correct	850 ms	10100 KB	Output is correct
18	Correct	687 ms	10100 KB	Output is correct
19	Correct	1245 ms	12608 KB	Output is correct
20	Correct	2900 ms	6404 KB	Output is correct
21	Correct	349 ms	1388 KB	Output is correct
22	Correct	3273 ms	8912 KB	Output is correct
23	Correct	1064 ms	18284 KB	Output is correct
24	Correct	1307 ms	11024 KB	Output is correct
25	Correct	2072 ms	18284 KB	Output is correct
26	Correct	1831 ms	18284 KB	Output is correct
27	Correct	1608 ms	18284 KB	Output is correct
28	Correct	1073 ms	248624 KB	Output is correct
29	Memory limit exceeded	2291 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

답안 #13374

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0