답안 #706228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706228	2023-03-06T06:56:02 Z	sharaelong	게임 (IOI13_game)	C++17	100 / 100	4030 ms	102628 KB

game

#include "game.h"
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

struct Node1 {
    int n, ln, rn; // left node, right node
    Node1() : n(-1), ln(-1), rn(-1) {}
};

struct Node2 {
    int ln, rn, latest;
    ll val;
    Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
};

int R, C;
vector<Node1> node1;
vector<Node2> node2;

int new_node1() {
    node1.push_back(Node1());
    return node1.size()-1;
}

int new_node2() {
    node2.push_back(Node2());
    return node2.size()-1;
}

void update2(int n, int nl, int nr, int y, ll v) {
    if (nl == nr) {
        node2[n].val = v;
        return;
    }

    int mid = (nl + nr) / 2;
    if (node2[n].latest != -1) {
        if (node2[n].latest <= mid) {
            node2[n].ln = new_node2();
            node2[node2[n].ln].latest = node2[n].latest;
            node2[node2[n].ln].val = node2[n].val;
        } else {
            node2[n].rn = new_node2();
            node2[node2[n].rn].latest = node2[n].latest;
            node2[node2[n].rn].val = node2[n].val;
        }
        node2[n].latest = -1;
    }
    
    if (y <= mid) {
        if (node2[n].ln == -1) {
            node2[n].ln = new_node2();
            node2[node2[n].ln].latest = y;
            node2[node2[n].ln].val = v;
        } else {
            update2(node2[n].ln, nl, mid, y, v);
        }
    } else {
        if (node2[n].rn == -1) {
            node2[n].rn = new_node2();
            node2[node2[n].rn].latest = y;
            node2[node2[n].rn].val = v;
        } else {
            update2(node2[n].rn, mid+1, nr, y, v);
        }
    }

    ll upd_gcd = 0;
    if (node2[n].ln != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].ln].val);
    if (node2[n].rn != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].rn].val);
    node2[n].val = upd_gcd;
}

ll query2(int n, int nl, int nr, int l, int r) {
    if (r < nl || nr < l) return 0;
    if (l <= nl && nr <= r) return node2[n].val;
    if (node2[n].latest != -1) {
        return (l <= node2[n].latest && node2[n].latest <= r ? node2[n].val : 0);
    }

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node2[n].ln != -1) ret = gcd2(ret, query2(node2[n].ln, nl, mid, l, r));
    if (node2[n].rn != -1) ret = gcd2(ret, query2(node2[n].rn, mid+1, nr, l, r));
    return ret;
}

void update1(int n, int nl, int nr, int x, int y, ll v) {
    if (node1[n].n == -1) node1[n].n = new_node2();
    if (nl == nr) {
        update2(node1[n].n, 0, C-1, y, v);
        return;
    }

    int mid = (nl + nr) / 2;
    if (x <= mid) {
        if (node1[n].ln == -1) node1[n].ln = new_node1();
        update1(node1[n].ln, nl, mid, x, y, v);
    } else {
        if (node1[n].rn == -1) node1[n].rn = new_node1();
        update1(node1[n].rn, mid+1, nr, x, y, v);
    }

    ll upd_gcd = 0;
    if (node1[n].ln != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].ln].n, 0, C-1, y, y));
    if (node1[n].rn != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].rn].n, 0, C-1, y, y));
    update2(node1[n].n, 0, C-1, y, upd_gcd);
}

ll query1(int n, int nl, int nr, int x1, int y1, int x2, int y2) {
    if (nr < x1 || x2 < nl) return 0;
    if (x1 <= nl && nr <= x2) return (node1[n].n != -1 ? query2(node1[n].n, 0, C-1, y1, y2) : 0);

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node1[n].ln != -1) ret = gcd2(ret, query1(node1[n].ln, nl, mid, x1, y1, x2, y2));
    if (node1[n].rn != -1) ret = gcd2(ret, query1(node1[n].rn, mid+1, nr, x1, y1, x2, y2));
    return ret;
}


int root;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    root = new_node1();
}

void update(int P, int Q, ll K) {
    update1(root, 0, R-1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return query1(root, 0, R-1, P, Q, U, V);
}

Compilation message

game.cpp: In constructor 'Node2::Node2()':
game.cpp:27:8: warning: 'Node2::val' will be initialized after [-Wreorder]
   27 |     ll val;
      |        ^~~
game.cpp:26:17: warning:   'int Node2::latest' [-Wreorder]
   26 |     int ln, rn, latest;
      |                 ^~~~~~
game.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
      |     ^~~~~

Subtask #1

10.0 / 10.0

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

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	397 ms	11372 KB	Output is correct
5	Correct	300 ms	11064 KB	Output is correct
6	Correct	348 ms	8568 KB	Output is correct
7	Correct	376 ms	8264 KB	Output is correct
8	Correct	264 ms	7492 KB	Output is correct
9	Correct	359 ms	8372 KB	Output is correct
10	Correct	330 ms	8100 KB	Output is correct
11	Correct	1 ms	296 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	296 KB	Output is correct
12	Correct	638 ms	12736 KB	Output is correct
13	Correct	1134 ms	7808 KB	Output is correct
14	Correct	244 ms	5588 KB	Output is correct
15	Correct	1380 ms	9504 KB	Output is correct
16	Correct	170 ms	10560 KB	Output is correct
17	Correct	539 ms	9296 KB	Output is correct
18	Correct	841 ms	11576 KB	Output is correct
19	Correct	725 ms	11652 KB	Output is correct
20	Correct	678 ms	11016 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	300 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	300 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	399 ms	11312 KB	Output is correct
13	Correct	282 ms	11120 KB	Output is correct
14	Correct	336 ms	8504 KB	Output is correct
15	Correct	366 ms	8244 KB	Output is correct
16	Correct	264 ms	7436 KB	Output is correct
17	Correct	359 ms	8344 KB	Output is correct
18	Correct	319 ms	8016 KB	Output is correct
19	Correct	647 ms	12976 KB	Output is correct
20	Correct	1156 ms	7816 KB	Output is correct
21	Correct	243 ms	5728 KB	Output is correct
22	Correct	1397 ms	9612 KB	Output is correct
23	Correct	174 ms	10700 KB	Output is correct
24	Correct	536 ms	8924 KB	Output is correct
25	Correct	836 ms	10704 KB	Output is correct
26	Correct	720 ms	10916 KB	Output is correct
27	Correct	754 ms	10260 KB	Output is correct
28	Correct	478 ms	30300 KB	Output is correct
29	Correct	1096 ms	40876 KB	Output is correct
30	Correct	3547 ms	29080 KB	Output is correct
31	Correct	3347 ms	51464 KB	Output is correct
32	Correct	502 ms	10456 KB	Output is correct
33	Correct	673 ms	12236 KB	Output is correct
34	Correct	240 ms	30092 KB	Output is correct
35	Correct	750 ms	24140 KB	Output is correct
36	Correct	1542 ms	33400 KB	Output is correct
37	Correct	1141 ms	39088 KB	Output is correct
38	Correct	1173 ms	38300 KB	Output is correct
39	Correct	952 ms	28392 KB	Output is correct
40	Correct	5 ms	212 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	296 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	401 ms	7984 KB	Output is correct
13	Correct	293 ms	8272 KB	Output is correct
14	Correct	350 ms	5280 KB	Output is correct
15	Correct	398 ms	4712 KB	Output is correct
16	Correct	277 ms	4428 KB	Output is correct
17	Correct	380 ms	4876 KB	Output is correct
18	Correct	385 ms	4576 KB	Output is correct
19	Correct	664 ms	10792 KB	Output is correct
20	Correct	1252 ms	5344 KB	Output is correct
21	Correct	380 ms	2520 KB	Output is correct
22	Correct	1489 ms	6788 KB	Output is correct
23	Correct	205 ms	7828 KB	Output is correct
24	Correct	541 ms	5864 KB	Output is correct
25	Correct	916 ms	8028 KB	Output is correct
26	Correct	792 ms	8592 KB	Output is correct
27	Correct	747 ms	7832 KB	Output is correct
28	Correct	439 ms	29216 KB	Output is correct
29	Correct	1103 ms	40752 KB	Output is correct
30	Correct	3514 ms	29180 KB	Output is correct
31	Correct	3230 ms	51464 KB	Output is correct
32	Correct	466 ms	10456 KB	Output is correct
33	Correct	1124 ms	12236 KB	Output is correct
34	Correct	233 ms	30092 KB	Output is correct
35	Correct	704 ms	24092 KB	Output is correct
36	Correct	1368 ms	33440 KB	Output is correct
37	Correct	1174 ms	39128 KB	Output is correct
38	Correct	1309 ms	38260 KB	Output is correct
39	Correct	579 ms	65864 KB	Output is correct
40	Correct	1667 ms	68560 KB	Output is correct
41	Correct	4030 ms	54168 KB	Output is correct
42	Correct	3970 ms	102628 KB	Output is correct
43	Correct	400 ms	59576 KB	Output is correct
44	Correct	663 ms	10948 KB	Output is correct
45	Correct	886 ms	28460 KB	Output is correct
46	Correct	1731 ms	66740 KB	Output is correct
47	Correct	1709 ms	66768 KB	Output is correct
48	Correct	1709 ms	66480 KB	Output is correct
49	Correct	0 ms	304 KB	Output is correct