답안 #582803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582803	2022-06-24T13:03:24 Z	vot808	게임 (IOI13_game)	C++17	100 / 100	2664 ms	42900 KB

game

#include "bits/stdc++.h"
#include "game.h"
#ifdef mlocal
#include "grader.c"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'
 
int MXR, MXC;
 
struct SegmentTree {
	public:
	vector<ii> c;
	vi l, r;
	vector<ll> tree;
	int pt = 1;
	
	void update(int &i, ll val, int p) {
		// cout << "updating in y range " << l[p] << " " << r[p] << " at index " << i << endl;
		if (l[p] == r[p]) {
			// cout << "/// setting leaf to " << val << endl;
			tree[p] = val;
			return;
		}
		
		int mid = (l[p]+r[p])/2, s = i > mid;
		if (!c[p][s]) {
			// Key memory heuristic: if no child in this direction, then ONLY create the leaf node and NOT all intervals
			// Deserves a CF Blog? :P
			tree.resize(pt+1); c.resize(pt+1); l.push_back(i); r.push_back(i);
			// cout << "!! creating leaf node " << i << " " << i << " on side " << s << endl;
			c[p][s] = pt++;
		} else if (l[c[p][s]] > i or r[c[p][s]] < i) {
			// If there already exists a node in this direction and this is not the interval we need, 
			// then find the last interval such that this existing node and the new leaf node lie on different sides.
			// It then reduces to the previous case for this newly create interval node.
			
			// cout << "y child exists but not correct range cuz currently is " << l[c[p][s]] << " " << r[c[p][s]] << endl;
			int cl = l[p], cr = r[p], cmid = (cl+cr)/2;
			while (!((r[c[p][s]] <= cmid) ^ (i <= cmid))) {
				if (i <= cmid) cr = cmid;
				else cl = cmid+1;
				cmid = (cl+cr)/2;
			}
			
			// cout << "~~~ creating " << cl << " " << cr << " and attaching " << l[c[p][s]] << " " << r[c[p][s]] << " to " << (r[c[p][s]] > cmid) << endl;
			tree.resize(pt+1); c.resize(pt+1); l.push_back(cl); r.push_back(cr);
			c[pt][r[c[p][s]] > cmid] = c[p][s];
			c[p][s] = pt++;
		}
		
		update(i, val, c[p][s]);
		tree[p] = __gcd(c[p][0] ? tree[c[p][0]] : 0, c[p][1] ? tree[c[p][1]] : 0);
	}
	
	ll query(int &i, int &j, int p) {
		if (l[p] > j or r[p] < i) return 0;
		// cout << "in y range " << l[p] << " " << r[p] << " for query range " << i << " " << j << endl;
		// if (c[p][0]) cout << "\thas left child " << l[c[p][0]] << " " << r[c[p][0]] << endl;
		// if (c[p][1]) cout << "\thas right child " << l[c[p][1]] << " " << r[c[p][1]] << endl;
		
		if (l[p] >= i and r[p] <= j) {
			// cout << "y range " << l[p] << " " << r[p] << " gives " << tree[p] << endl;
			return tree[p];
		}
		
		return __gcd(c[p][0] ? query(i, j, c[p][0]) : 0, c[p][1] ? query(i, j, c[p][1]) : 0);
	}
	
	SegmentTree() {
		c.resize(1); tree.resize(1); l.push_back(0); r.push_back(MXC);
	}
};
 
struct SegmentTree2D {
	public:
	vector<ii> c;
	vi l, r;
	vector<SegmentTree> tree;
	int pt = 1;
	
	void update(int &i, int &j, ll val, int p) {
		// cout << "updating x range " << l[p] << " " << r[p] << endl;
		// if (c[p][0]) cout << "---------\thas left child " << l[c[p][0]] << " " << r[c[p][0]] << endl;
		// if (c[p][1]) cout << "---------\thas right child " << l[c[p][1]] << " " << r[c[p][1]] << endl;
		if (l[p] != r[p]) {
			int mid = (l[p]+r[p])/2, s = i > mid;
			// Same heuristic as above
			if (!c[p][s]) {
				tree.resize(pt+1); c.resize(pt+1); l.push_back(i); r.push_back(i);
				c[p][s] = pt++;
			} else if (l[c[p][s]] > i or r[c[p][s]] < i) {
				int cl = l[p], cr = r[p], cmid = (cl+cr)/2;
				while (!((r[c[p][s]] <= cmid) ^ (i <= cmid))) {
					if (i <= cmid) cr = cmid;
					else cl = cmid+1;
					cmid = (cl+cr)/2;
				}
				
				tree.push_back(tree[c[p][s]]); c.resize(pt+1); l.push_back(cl); r.push_back(cr);
				c[pt][r[c[p][s]] > cmid] = c[p][s];
				c[p][s] = pt++;
			}
			
			update(i, j, val, c[p][s]);
		}
		
		if (l[p] != r[p]) val = __gcd(c[p][0] ? tree[c[p][0]].query(j, j, 0) : 0, c[p][1] ? tree[c[p][1]].query(j, j, 0) : 0);
		
		// cout << "going to y ranges of " << l[p] << " " << r[p] << endl;
		tree[p].update(j, val, 0);
	}
	
	ll query(int &xi, int &xj, int &yi, int &yj, int p) {
		if (l[p] > xj or r[p] < xi) return 0;
		if (l[p] >= xi and r[p] <= xj) {
			// cout << "querying x range " << l[p] << " " << r[p] << endl;
			return tree[p].query(yi, yj, 0);
		}
		
		return __gcd(c[p][0] ? query(xi, xj, yi, yj, c[p][0]) : 0, c[p][1] ? query(xi, xj, yi, yj, c[p][1]) : 0);
	}
	
	void build() {
		c.resize(1); tree.resize(1); l.push_back(0); r.push_back(MXR);
	}
};
 
SegmentTree2D tree;
 
void init(int R, int C) {
	// Wait, do I even need to do something here? :)
	MXR = R, MXC = C;
	tree.build();
}
 
void update(int P, int Q, ll K) {
	// cout << "------new update" << endl;
	tree.update(P, Q, K, 0);
}
 
ll calculate(int P, int Q, int U, int V) {
	return tree.query(P, U, Q, V, 0);
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	300 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	292 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	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	212 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	453 ms	11752 KB	Output is correct
5	Correct	333 ms	11460 KB	Output is correct
6	Correct	407 ms	8572 KB	Output is correct
7	Correct	471 ms	8372 KB	Output is correct
8	Correct	314 ms	7380 KB	Output is correct
9	Correct	431 ms	8428 KB	Output is correct
10	Correct	496 ms	8128 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	296 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	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	300 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	770 ms	14292 KB	Output is correct
13	Correct	1287 ms	8004 KB	Output is correct
14	Correct	209 ms	5520 KB	Output is correct
15	Correct	1419 ms	9508 KB	Output is correct
16	Correct	569 ms	12356 KB	Output is correct
17	Correct	641 ms	10340 KB	Output is correct
18	Correct	1142 ms	13716 KB	Output is correct
19	Correct	971 ms	13848 KB	Output is correct
20	Correct	853 ms	13332 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct

Subtask #4

17.0 / 17.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	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	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	525 ms	11600 KB	Output is correct
13	Correct	323 ms	11344 KB	Output is correct
14	Correct	425 ms	8640 KB	Output is correct
15	Correct	454 ms	8384 KB	Output is correct
16	Correct	336 ms	7472 KB	Output is correct
17	Correct	474 ms	8392 KB	Output is correct
18	Correct	388 ms	7928 KB	Output is correct
19	Correct	904 ms	14192 KB	Output is correct
20	Correct	1286 ms	7952 KB	Output is correct
21	Correct	240 ms	5552 KB	Output is correct
22	Correct	1442 ms	9536 KB	Output is correct
23	Correct	592 ms	12196 KB	Output is correct
24	Correct	623 ms	10316 KB	Output is correct
25	Correct	1010 ms	13720 KB	Output is correct
26	Correct	855 ms	13864 KB	Output is correct
27	Correct	825 ms	13336 KB	Output is correct
28	Correct	380 ms	24068 KB	Output is correct
29	Correct	984 ms	26924 KB	Output is correct
30	Correct	1809 ms	17336 KB	Output is correct
31	Correct	1747 ms	14820 KB	Output is correct
32	Correct	248 ms	10028 KB	Output is correct
33	Correct	333 ms	10140 KB	Output is correct
34	Correct	685 ms	20868 KB	Output is correct
35	Correct	766 ms	17388 KB	Output is correct
36	Correct	1524 ms	24836 KB	Output is correct
37	Correct	1152 ms	25072 KB	Output is correct
38	Correct	1115 ms	24532 KB	Output is correct
39	Correct	932 ms	21208 KB	Output is correct
40	Correct	1 ms	212 KB	Output is correct

Subtask #5

20.0 / 20.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	304 KB	Output is correct
4	Correct	1 ms	304 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	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	456 ms	11564 KB	Output is correct
13	Correct	333 ms	11460 KB	Output is correct
14	Correct	382 ms	8632 KB	Output is correct
15	Correct	486 ms	8320 KB	Output is correct
16	Correct	323 ms	7428 KB	Output is correct
17	Correct	420 ms	8420 KB	Output is correct
18	Correct	398 ms	7904 KB	Output is correct
19	Correct	812 ms	14180 KB	Output is correct
20	Correct	1301 ms	8156 KB	Output is correct
21	Correct	208 ms	5576 KB	Output is correct
22	Correct	1441 ms	9576 KB	Output is correct
23	Correct	566 ms	12332 KB	Output is correct
24	Correct	658 ms	10404 KB	Output is correct
25	Correct	1161 ms	13672 KB	Output is correct
26	Correct	1002 ms	13876 KB	Output is correct
27	Correct	812 ms	13372 KB	Output is correct
28	Correct	486 ms	24080 KB	Output is correct
29	Correct	1083 ms	26752 KB	Output is correct
30	Correct	1878 ms	17240 KB	Output is correct
31	Correct	1713 ms	14928 KB	Output is correct
32	Correct	234 ms	10076 KB	Output is correct
33	Correct	347 ms	10240 KB	Output is correct
34	Correct	739 ms	20716 KB	Output is correct
35	Correct	782 ms	17400 KB	Output is correct
36	Correct	1696 ms	24908 KB	Output is correct
37	Correct	1141 ms	25032 KB	Output is correct
38	Correct	1092 ms	24640 KB	Output is correct
39	Correct	634 ms	40524 KB	Output is correct
40	Correct	1870 ms	42900 KB	Output is correct
41	Correct	2664 ms	29676 KB	Output is correct
42	Correct	2378 ms	23620 KB	Output is correct
43	Correct	1031 ms	37600 KB	Output is correct
44	Correct	280 ms	10564 KB	Output is correct
45	Correct	945 ms	20968 KB	Output is correct
46	Correct	2300 ms	41772 KB	Output is correct
47	Correct	2240 ms	41944 KB	Output is correct
48	Correct	1975 ms	41392 KB	Output is correct
49	Correct	1 ms	212 KB	Output is correct