답안 #13372 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13372	2015-02-14T04:37:45 Z	dohyun0324	게임 (IOI13_game)	C++	63 / 100	3430 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	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	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	761 ms	14192 KB	Output is correct
5	Correct	554 ms	14192 KB	Output is correct
6	Correct	816 ms	14456 KB	Output is correct
7	Correct	957 ms	14456 KB	Output is correct
8	Correct	623 ms	8648 KB	Output is correct
9	Correct	902 ms	14588 KB	Output is correct
10	Correct	768 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	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	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	1269 ms	18284 KB	Output is correct
13	Correct	2978 ms	8912 KB	Output is correct
14	Correct	390 ms	1388 KB	Output is correct
15	Correct	3430 ms	12608 KB	Output is correct
16	Correct	1079 ms	26864 KB	Output is correct
17	Correct	1394 ms	15908 KB	Output is correct
18	Correct	2320 ms	26864 KB	Output is correct
19	Correct	2069 ms	26864 KB	Output is correct
20	Correct	1840 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	1 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	1 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	746 ms	14192 KB	Output is correct
13	Correct	535 ms	14192 KB	Output is correct
14	Correct	823 ms	14456 KB	Output is correct
15	Correct	899 ms	14456 KB	Output is correct
16	Correct	609 ms	8648 KB	Output is correct
17	Correct	876 ms	14588 KB	Output is correct
18	Correct	747 ms	14456 KB	Output is correct
19	Correct	1249 ms	18284 KB	Output is correct
20	Correct	3018 ms	8912 KB	Output is correct
21	Correct	384 ms	1388 KB	Output is correct
22	Correct	3278 ms	12608 KB	Output is correct
23	Correct	1124 ms	26864 KB	Output is correct
24	Correct	1455 ms	15908 KB	Output is correct
25	Correct	2340 ms	26864 KB	Output is correct
26	Correct	2022 ms	26864 KB	Output is correct
27	Correct	1848 ms	26864 KB	Output is correct
28	Memory limit exceeded	716 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	1 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	746 ms	14192 KB	Output is correct
13	Correct	512 ms	14192 KB	Output is correct
14	Correct	829 ms	14456 KB	Output is correct
15	Correct	910 ms	14456 KB	Output is correct
16	Correct	618 ms	8648 KB	Output is correct
17	Correct	894 ms	14588 KB	Output is correct
18	Correct	741 ms	14456 KB	Output is correct
19	Correct	1274 ms	18284 KB	Output is correct
20	Correct	3001 ms	8912 KB	Output is correct
21	Correct	368 ms	1388 KB	Output is correct
22	Correct	3384 ms	12608 KB	Output is correct
23	Correct	1094 ms	26864 KB	Output is correct
24	Correct	1386 ms	15908 KB	Output is correct
25	Correct	2284 ms	26864 KB	Output is correct
26	Correct	2024 ms	26864 KB	Output is correct
27	Correct	1848 ms	26864 KB	Output is correct
28	Memory limit exceeded	679 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #13372

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