제출 #1303696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303696		thieunguyenhuy	게임 (IOI13_game)	C++20	0 / 100	119 ms	235220 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct SegmentTree {
	struct Node {
		ll value;
		int ch[2][2];

		Node() {
			value = 0;
			memset(ch, -1, sizeof(ch));
		}
	};

	static const int NUM_NODES = 1e7;
	int root, cnt_node; Node t[NUM_NODES];
	int n, m;

	SegmentTree() {}

	void init(int n_, int m_) {
		cnt_node = 0;
		root = ++cnt_node;
		n = n_; m = m_;
	}

	void update(int id, int l1, int r1, int l2, int r2, int x1, int x2, ll value) {
		if (l1 == r1 && l2 == r2) {
			t[id].value = value;
			return;
		}

		int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;

		if (x1 <= mid1) {
			if (x2 <= mid2) {
				if (t[id].ch[0][0] == -1) t[id].ch[0][0] = ++cnt_node;
				update(t[id].ch[0][0], l1, mid1, l2, mid2, x1, x2, value);
			}
			else {
				if (t[id].ch[0][1] == -1) t[id].ch[0][1] = ++cnt_node;
				update(t[id].ch[0][1], l1, mid1, mid2 + 1, r2, x1, x2, value);
			}
		}
		else {
			if (x2 <= mid2) {
				if (t[id].ch[1][0] == -1) t[id].ch[1][0] = ++cnt_node;
				update(t[id].ch[1][0], mid1 + 1, r1, l2, mid2, x1, x2, value);
			}
			else {
				if (t[id].ch[1][1] == -1) t[id].ch[1][1] = ++cnt_node;
				update(t[id].ch[1][1], mid1 + 1, r1, mid2 + 1, r2, x1, x2, value);
			}
		}

		ll res = 0;

		for (int c1 = 0; c1 <= 1; c1++) {
			for (int c2 = 0; c2 <= 1; c2++) {
				int c = t[id].ch[c1][c2];
				if (c != -1) res = __gcd(res, t[c].value);
			}
		}

		t[id].value = res;
	}

	void update(int x, int y, ll value) {
		return update(root, 1, n, 1, m, x, y, value);
	}

	bool check(int l1, int r1, int l2, int r2, int u1, int v1, int u2, int v2) {
		if (l1 > v1 || r1 < u1 || l2 > v2 || r2 < u2) return 0;
		return 1;
	}

	ll get(int id, int l1, int r1, int l2, int r2, int u1, int v1, int u2, int v2) {
		if (id == -1 || !check(l1, r1, l2, r2, u1, v1, u2, v2)) {
			return 0;
		}
		if (u1 <= l1 && r1 <= v1 && u2 <= l2 && r2 <= v2) {
			return t[id].value;
		}

		int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;

		ll res = 0;

		if (t[id].ch[0][0] != -1 && check(l1, mid1, l2, mid2, u1, v1, u2, v2)) {
			res = __gcd(res, get(t[id].ch[0][0], l1, mid1, l2, mid2, u1, v1, u2, v2));
		}
		if (t[id].ch[0][1] != -1 && check(l1, mid1, mid2 + 1, r2, u1, v1, u2, v2)) {
			res = __gcd(res, get(t[id].ch[0][1], l1, mid1, mid2 + 1, r2, u1, v1, u2, v2));
		}
		if (t[id].ch[1][0] != -1 && check(mid1 + 1, l1, l2, mid2, u1, v1, u2, v2)) {
			res = __gcd(res, get(t[id].ch[1][0], mid1 + 1, r1, l2, mid2, u1, v1, u2, v2));
		}
		if (t[id].ch[1][1] != -1 && check(mid1 + 1, r1, mid2 + 1, r2, u1, v1, u2, v2)) {
			res = __gcd(res, get(t[id].ch[1][1], mid1 + 1, r1, mid2 + 1, r2, u1, v1, u2, v2));
		}

		return res;
	}

	ll get(int x, int y, int u, int v) {
		return get(root, 1, n, 1, m, x, u, y, v);
	}
} st;

void init(int r, int c) {
	st.init(r, c);
}

void update(int p, int q, ll k) {
	st.update(p + 1, q + 1, k);
}

ll calculate(int p, int q, int u, int v) {
	return st.get(p + 1, q + 1, u + 1, v + 1);
}

#ifdef hwe
signed main() {
	cin.tie(0) -> sync_with_stdio(0);

	int T = 1; // cin >> T;
	while (T--) {
		solve();
	}
}
#endif

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20