답안 #13375 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13375	2015-02-14T05:31:43 Z	dohyun0324	게임 (IOI13_game)	C++	63 / 100	3330 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 rx,ry;
    data *l,*r;
    data(int s,int e):rx(s),ry(e){
        l=r=NULL;
    }
    void update3()
    {
        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->rx=rx; l->ry=mid; l->update3();
        }
        else
        {
            if(r==NULL) r=new data(mid+1,ry);
            r->rx=mid+1; r->ry=ry; r->update3();
        }
        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 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)
        {
            r->rx=mid+1; r->ry=ry;
            return r->query();
        }
        else if(r==NULL)
        {
            l->rx=rx; l->ry=mid;
            return l->query();
        }
        l->rx=rx; l->ry=mid;
        r->rx=mid+1; r->ry=ry;
        return gcd2(l->query(),r->query());
    }
    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);
};
data start=data(1,n);
void init(int R, int C){
    n=R+1, m=C+1;
    start=data(1,n);
}
void update(int P, int Q, ll K){
    x1=P+1; y1=Q+1; k=K;
    start.update3();
}
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();
}

Subtask #1
10.0 / 10.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	1 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	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	745 ms	9836 KB	Output is correct
5	Correct	511 ms	9836 KB	Output is correct
6	Correct	807 ms	10100 KB	Output is correct
7	Correct	840 ms	10100 KB	Output is correct
8	Correct	539 ms	6140 KB	Output is correct
9	Correct	861 ms	10100 KB	Output is correct
10	Correct	733 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	1 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	1 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	1204 ms	12608 KB	Output is correct
13	Correct	2931 ms	6404 KB	Output is correct
14	Correct	357 ms	1388 KB	Output is correct
15	Correct	3330 ms	8912 KB	Output is correct
16	Correct	1109 ms	18416 KB	Output is correct
17	Correct	1314 ms	11024 KB	Output is correct
18	Correct	2095 ms	18416 KB	Output is correct
19	Correct	1805 ms	18416 KB	Output is correct
20	Correct	1655 ms	18416 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	1 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	703 ms	9836 KB	Output is correct
13	Correct	511 ms	9836 KB	Output is correct
14	Correct	797 ms	10100 KB	Output is correct
15	Correct	881 ms	10100 KB	Output is correct
16	Correct	547 ms	6140 KB	Output is correct
17	Correct	840 ms	10100 KB	Output is correct
18	Correct	687 ms	10100 KB	Output is correct
19	Correct	1200 ms	12608 KB	Output is correct
20	Correct	2940 ms	6404 KB	Output is correct
21	Correct	351 ms	1388 KB	Output is correct
22	Correct	3318 ms	8912 KB	Output is correct
23	Correct	1085 ms	18416 KB	Output is correct
24	Correct	1265 ms	11024 KB	Output is correct
25	Correct	2080 ms	18416 KB	Output is correct
26	Correct	1816 ms	18416 KB	Output is correct
27	Correct	1650 ms	18416 KB	Output is correct
28	Correct	1088 ms	251396 KB	Output is correct
29	Memory limit exceeded	2256 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	723 ms	9836 KB	Output is correct
13	Correct	537 ms	9836 KB	Output is correct
14	Correct	763 ms	10100 KB	Output is correct
15	Correct	818 ms	10100 KB	Output is correct
16	Correct	555 ms	6140 KB	Output is correct
17	Correct	830 ms	10100 KB	Output is correct
18	Correct	696 ms	10100 KB	Output is correct
19	Correct	1263 ms	12608 KB	Output is correct
20	Correct	2901 ms	6404 KB	Output is correct
21	Correct	383 ms	1388 KB	Output is correct
22	Correct	3316 ms	8912 KB	Output is correct
23	Correct	1092 ms	18416 KB	Output is correct
24	Correct	1326 ms	11024 KB	Output is correct
25	Correct	2056 ms	18416 KB	Output is correct
26	Correct	1822 ms	18416 KB	Output is correct
27	Correct	1633 ms	18416 KB	Output is correct
28	Correct	1069 ms	251396 KB	Output is correct
29	Memory limit exceeded	2238 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

답안 #13375

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