답안 #13373 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13373	2015-02-14T04:42:09 Z	dohyun0324	게임 (IOI13_game)	C++	63 / 100	3405 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
{
    int rs,re;
    data *l,*r;
    data(){}
    data(int s,int e):rs(s),re(e){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(rx,mid);
            l->update3(rx,mid);
        }
        else
        {
            if(r==NULL) r=new data(mid+1,ry);
            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
    {
        int cs,ce; ll val;
        data2 *l,*r;
        data2(){}
        data2(int s,int e,ll v):cs(s),ce(e),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(cx,mid,0);
                l->update2(cx,mid);
            }
            else{
                if(r==NULL) r=new data2(mid+1,cy,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(1,m,0);
};
void init(int R, int C){
    n=R+1, m=C+1;
}
data start=data(1,n);
void update(int P, int Q, ll K){
    P++; Q++;
    x1=P; y1=Q; 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	0 ms	1256 KB	Output is correct
2	Correct	1 ms	1388 KB	Output is correct
3	Correct	0 ms	1388 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	1388 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	1388 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	1 ms	1256 KB	Output is correct
12	Correct	0 ms	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	754 ms	14192 KB	Output is correct
5	Correct	519 ms	14192 KB	Output is correct
6	Correct	837 ms	14456 KB	Output is correct
7	Correct	897 ms	14456 KB	Output is correct
8	Correct	593 ms	8648 KB	Output is correct
9	Correct	910 ms	14588 KB	Output is correct
10	Correct	754 ms	14456 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	1388 KB	Output is correct
3	Correct	0 ms	1388 KB	Output is correct
4	Correct	0 ms	1256 KB	Output is correct
5	Correct	0 ms	1256 KB	Output is correct
6	Correct	1 ms	1388 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	1388 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	0 ms	1256 KB	Output is correct
12	Correct	1255 ms	18284 KB	Output is correct
13	Correct	2993 ms	8912 KB	Output is correct
14	Correct	372 ms	1388 KB	Output is correct
15	Correct	3405 ms	12608 KB	Output is correct
16	Correct	1070 ms	26864 KB	Output is correct
17	Correct	1385 ms	15908 KB	Output is correct
18	Correct	2334 ms	26864 KB	Output is correct
19	Correct	2093 ms	26864 KB	Output is correct
20	Correct	1849 ms	26864 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	1388 KB	Output is correct
3	Correct	1 ms	1388 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	1388 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	1388 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	0 ms	1256 KB	Output is correct
12	Correct	743 ms	14192 KB	Output is correct
13	Correct	499 ms	14192 KB	Output is correct
14	Correct	804 ms	14456 KB	Output is correct
15	Correct	909 ms	14456 KB	Output is correct
16	Correct	605 ms	8648 KB	Output is correct
17	Correct	867 ms	14588 KB	Output is correct
18	Correct	761 ms	14456 KB	Output is correct
19	Correct	1258 ms	18284 KB	Output is correct
20	Correct	2992 ms	8912 KB	Output is correct
21	Correct	377 ms	1388 KB	Output is correct
22	Correct	3309 ms	12608 KB	Output is correct
23	Correct	1113 ms	26864 KB	Output is correct
24	Correct	1403 ms	15908 KB	Output is correct
25	Correct	2331 ms	26864 KB	Output is correct
26	Correct	1934 ms	26864 KB	Output is correct
27	Correct	1841 ms	26864 KB	Output is correct
28	Memory limit exceeded	743 ms	256000 KB	Memory limit exceeded
29	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	1388 KB	Output is correct
3	Correct	0 ms	1388 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	1388 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	1388 KB	Output is correct
10	Correct	0 ms	1256 KB	Output is correct
11	Correct	0 ms	1256 KB	Output is correct
12	Correct	737 ms	14192 KB	Output is correct
13	Correct	516 ms	14192 KB	Output is correct
14	Correct	819 ms	14456 KB	Output is correct
15	Correct	942 ms	14456 KB	Output is correct
16	Correct	614 ms	8648 KB	Output is correct
17	Correct	904 ms	14588 KB	Output is correct
18	Correct	781 ms	14456 KB	Output is correct
19	Correct	1267 ms	18284 KB	Output is correct
20	Correct	2983 ms	8912 KB	Output is correct
21	Correct	358 ms	1388 KB	Output is correct
22	Correct	3376 ms	12608 KB	Output is correct
23	Correct	1092 ms	26864 KB	Output is correct
24	Correct	1407 ms	15908 KB	Output is correct
25	Correct	2302 ms	26864 KB	Output is correct
26	Correct	2043 ms	26864 KB	Output is correct
27	Correct	1871 ms	26864 KB	Output is correct
28	Memory limit exceeded	637 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #13373

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