답안 #15777 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15777	2015-07-24T14:51:36 Z	ainta	게임 (IOI13_game)	C++	63 / 100	3425 ms	256000 KB

game

#include "game.h"
#include<stdio.h>
#include<algorithm>
using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct SegY{
    long long G;
    SegY *c1, *c2;
    SegY(){
        G=0;
        c1=c2=NULL;
    }
};

struct SegX{
    long long G;
    SegX *c1, *c2;
    SegY *cy;
    SegX(){
        G=0;
        c1=c2=NULL;
        cy=NULL;
    }
};

SegX *rootX;
SegY *rootY;

int MR, MC;



void init(int R, int C) {
    rootX = new SegX();
    rootY = new SegY();
    MR = R, MC = C;
}

void InsY(SegY *nd, int b, int e, int y, long long K){
    if(b==e){
        nd->G = K;
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1){
        nd->c1 = new SegY();
        nd->c2 = new SegY();
    }
    if(y <= m)InsY(nd->c1, b, m, y, K);
    else InsY(nd->c2, m+1, e, y, K);
    nd->G = gcd2(nd->c1->G, nd->c2->G);
}

void UDT(SegY *nd, SegY *nd1, SegY *nd2, int b, int e, int y){
    nd->G = gcd2(nd1?nd1->G:0, nd2?nd2->G:0);
    if(b==e)return;
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1 = new SegY(), nd->c2 = new SegY();
    if(y <= m)UDT(nd->c1, nd1?nd1->c1:NULL, nd2?nd2->c1:NULL, b, m, y);
    else UDT(nd->c2, nd1?nd1->c2:NULL, nd2?nd2->c2:NULL, m+1, e, y);
}

void InsX(SegX *nd, int b, int e, int x, int y, long long K){
    if(b==e){
        if(!nd->cy)nd->cy = new SegY();
        InsY(nd->cy, 0, MC - 1, y, K);
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1 = new SegX(), nd->c2 = new SegX();
    if(!nd->cy)nd->cy = new SegY();
    if(x <= m) InsX(nd->c1, b, m, x, y, K);
    else InsX(nd->c2, m+1, e, x, y, K);
    UDT(nd->cy, nd->c1->cy, nd->c2->cy, 0, MC - 1, y);
}

void update(int P, int Q, long long K) {
    InsX(rootX, 0, MR - 1, P, Q, K);
}

long long CalcY(SegY *nd, int b, int e, int s, int l){
    if(!nd)return 0;
    if(b == s && e == l)return nd->G;
    int m = (b+e)>>1;
    long long r = 0;
    if(s <= m && nd->c1) r = CalcY(nd->c1, b, m, s, min(m,l));
    if(l > m && nd->c2) r = gcd2(CalcY(nd->c2, m + 1, e, max(s, m+1), l), r);
    return r;
}

long long CalcX(SegX *nd, int b, int e, int s, int l, int by, int ey){
    if(b == s && e == l)return CalcY(nd->cy, 0, MC - 1, by, ey);
    int m = (b+e)>>1;
    long long r = 0;
    if(s <= m && nd->c1) r = CalcX(nd->c1, b, m, s, min(m,l), by, ey);
    if(l > m && nd->c2) r = gcd2(CalcX(nd->c2, m+1, e, max(m+1, s), l, by, ey), r);
    return r;
}

long long calculate(int P, int Q, int U, int V) {
    return CalcX(rootX, 0, MR - 1, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1212 KB	Output is correct
2	Correct	1344 KB	Output is correct
3	Correct	1344 KB	Output is correct
4	Correct	1212 KB	Output is correct
5	Correct	1212 KB	Output is correct
6	Correct	1344 KB	Output is correct
7	Correct	1212 KB	Output is correct
8	Correct	1212 KB	Output is correct
9	Correct	1344 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	806 ms	15072 KB	Output is correct
5	Correct	568 ms	15072 KB	Output is correct
6	Correct	741 ms	15468 KB	Output is correct
7	Correct	843 ms	15468 KB	Output is correct
8	Correct	585 ms	9396 KB	Output is correct
9	Correct	821 ms	15468 KB	Output is correct
10	Correct	682 ms	15336 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	0 ms	1344 KB	Output is correct
3	Correct	1 ms	1344 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	1344 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	1344 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	1 ms	1212 KB	Output is correct
12	Correct	1239 ms	19296 KB	Output is correct
13	Correct	2828 ms	8736 KB	Output is correct
14	Correct	402 ms	1344 KB	Output is correct
15	Correct	3425 ms	13092 KB	Output is correct
16	Correct	348 ms	29592 KB	Output is correct
17	Correct	1431 ms	17844 KB	Output is correct
18	Correct	2175 ms	29592 KB	Output is correct
19	Correct	1943 ms	29592 KB	Output is correct
20	Correct	1753 ms	29592 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1344 KB	Output is correct
3	Correct	0 ms	1344 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	1 ms	1212 KB	Output is correct
6	Correct	0 ms	1344 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	1344 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	816 ms	15072 KB	Output is correct
13	Correct	553 ms	15072 KB	Output is correct
14	Correct	801 ms	15468 KB	Output is correct
15	Correct	877 ms	15468 KB	Output is correct
16	Correct	553 ms	9396 KB	Output is correct
17	Correct	793 ms	15468 KB	Output is correct
18	Correct	701 ms	15336 KB	Output is correct
19	Correct	1271 ms	19296 KB	Output is correct
20	Correct	2837 ms	8736 KB	Output is correct
21	Correct	459 ms	1344 KB	Output is correct
22	Correct	3354 ms	13092 KB	Output is correct
23	Correct	310 ms	29592 KB	Output is correct
24	Correct	1385 ms	17844 KB	Output is correct
25	Correct	2254 ms	29592 KB	Output is correct
26	Correct	1966 ms	29592 KB	Output is correct
27	Correct	1804 ms	29592 KB	Output is correct
28	Memory limit exceeded	662 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1344 KB	Output is correct
3	Correct	0 ms	1344 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	1344 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	1344 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	1 ms	1212 KB	Output is correct
12	Correct	858 ms	15072 KB	Output is correct
13	Correct	548 ms	15072 KB	Output is correct
14	Correct	783 ms	15468 KB	Output is correct
15	Correct	880 ms	15468 KB	Output is correct
16	Correct	538 ms	9396 KB	Output is correct
17	Correct	827 ms	15468 KB	Output is correct
18	Correct	750 ms	15336 KB	Output is correct
19	Correct	1254 ms	19296 KB	Output is correct
20	Correct	2979 ms	8736 KB	Output is correct
21	Correct	450 ms	1344 KB	Output is correct
22	Correct	3422 ms	13092 KB	Output is correct
23	Correct	323 ms	29592 KB	Output is correct
24	Correct	1640 ms	17844 KB	Output is correct
25	Correct	2329 ms	29592 KB	Output is correct
26	Correct	1971 ms	29592 KB	Output is correct
27	Correct	2028 ms	29592 KB	Output is correct
28	Memory limit exceeded	673 ms	256000 KB	Memory limit exceeded
29	Halted	0 ms	0 KB	-

답안 #15777

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