답안 #626132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626132	2022-08-11T08:57:41 Z	PoonYaPat	게임 (IOI13_game)	C++14	37 / 100	13000 ms	256000 KB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int r,c;
map<pii,ll> s;

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;
}

ll gcd(ll x, ll y) {
    if (x==0) return y;
    if (y==0) return x;
    return gcd2(x,y);
}

void init(int R, int C) {
    r=R;
    c=C;
}

void update_y(int lx, int rx, int idx_x, int ly, int ry, int idx_y, int x, int y, ll val) {
    if (ly>y || ry<y) return;
    if (ly==ry) {
        if (lx==rx) {
            s[pii(idx_x,idx_y)]=val;
        } else {
            s[pii(idx_x,idx_y)]=gcd(s[pii(2*idx_x,idx_y)],s[pii(2*idx_x+1,idx_y)]);
        }
    } else {
        int mid=(ly+ry)/2;
        update_y(lx,rx,idx_x,ly,mid,2*idx_y,x,y,val);
        update_y(lx,rx,idx_x,mid+1,ry,2*idx_y+1,x,y,val);
        s[pii(idx_x,idx_y)]=gcd(s[pii(idx_x,2*idx_y)],s[pii(idx_x,2*idx_y+1)]);
    }
}

void update_x(int lx, int rx, int idx_x, int x, int y, ll val) {
    if (lx>x || rx<x) return;
    if (lx!=rx) {
        int mid=(lx+rx)/2;
        update_x(lx,mid,2*idx_x,x,y,val);
        update_x(mid+1,rx,2*idx_x+1,x,y,val);
    }
    update_y(lx,rx,idx_x,1,c,1,x,y,val);
}

void update(int P, int Q, long long K) {
    ++P; ++Q;
    update_x(1,r,1,P,Q,K);
}

ll query_y(int idx_x, int ly, int ry, int idx_y, int y1, int y2) {
    if (y1>ry || y2<ly) return 0;
    if (y1<=ly && ry<=y2) return s[pii(idx_x,idx_y)];
    int mid=(ly+ry)/2;
    return gcd(query_y(idx_x,ly,mid,2*idx_y,y1,y2),query_y(idx_x,mid+1,ry,2*idx_y+1,y1,y2));
}

ll query_x(int lx, int rx, int idx_x, int x1, int y1, int x2, int y2) {
    if (x1>rx || x2<lx) return 0;
    if (x1<=lx && rx<=x2) return query_y(idx_x,1,c,1,y1,y2);
    int mid=(lx+rx)/2;
    return gcd(query_x(lx,mid,2*idx_x,x1,y1,x2,y2),query_x(mid+1,rx,2*idx_x+1,x1,y1,x2,y2));
}

long long calculate(int P, int Q, int U, int V) {
    ++P; ++Q; ++U; ++V;
    if (P>U) swap(P,U);
    if (Q>V) swap(Q,V);
    return query_x(1,r,1,P,Q,U,V);
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	684 KB	Output is correct
3	Correct	4 ms	724 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	4 ms	684 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	4 ms	596 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	5263 ms	44676 KB	Output is correct
5	Correct	2892 ms	38508 KB	Output is correct
6	Correct	4800 ms	102560 KB	Output is correct
7	Correct	4828 ms	102360 KB	Output is correct
8	Correct	3848 ms	97356 KB	Output is correct
9	Correct	4838 ms	104496 KB	Output is correct
10	Correct	4702 ms	102108 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct

Subtask #3
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	4 ms	684 KB	Output is correct
3	Correct	5 ms	688 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	6430 ms	48272 KB	Output is correct
13	Correct	6432 ms	21532 KB	Output is correct
14	Correct	3475 ms	7536 KB	Output is correct
15	Correct	7609 ms	31360 KB	Output is correct
16	Correct	985 ms	66352 KB	Output is correct
17	Correct	10689 ms	252716 KB	Output is correct
18	Runtime error	10886 ms	256000 KB	Execution killed with signal 9
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	3 ms	724 KB	Output is correct
3	Correct	4 ms	700 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	3 ms	596 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	3 ms	596 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4066 ms	44648 KB	Output is correct
13	Correct	2454 ms	38540 KB	Output is correct
14	Correct	4925 ms	102592 KB	Output is correct
15	Correct	4431 ms	102360 KB	Output is correct
16	Correct	3567 ms	97388 KB	Output is correct
17	Correct	4306 ms	104524 KB	Output is correct
18	Correct	4641 ms	102052 KB	Output is correct
19	Correct	7004 ms	48272 KB	Output is correct
20	Correct	6188 ms	21568 KB	Output is correct
21	Correct	3894 ms	7420 KB	Output is correct
22	Correct	8636 ms	31344 KB	Output is correct
23	Correct	1024 ms	66312 KB	Output is correct
24	Correct	12139 ms	252748 KB	Output is correct
25	Execution timed out	13083 ms	256000 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	688 KB	Output is correct
3	Correct	4 ms	724 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	3 ms	692 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	3 ms	596 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	304 KB	Output is correct
12	Correct	4626 ms	44736 KB	Output is correct
13	Correct	2556 ms	38452 KB	Output is correct
14	Correct	4540 ms	102508 KB	Output is correct
15	Correct	4398 ms	102300 KB	Output is correct
16	Correct	3599 ms	97388 KB	Output is correct
17	Correct	4981 ms	104520 KB	Output is correct
18	Correct	4796 ms	102036 KB	Output is correct
19	Correct	6435 ms	48304 KB	Output is correct
20	Correct	5774 ms	21596 KB	Output is correct
21	Correct	3395 ms	7404 KB	Output is correct
22	Correct	7834 ms	31404 KB	Output is correct
23	Correct	965 ms	66308 KB	Output is correct
24	Correct	10673 ms	252836 KB	Output is correct
25	Runtime error	11169 ms	256000 KB	Execution killed with signal 9
26	Halted	0 ms	0 KB	-

답안 #626132

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0