제출 #582803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582803		vot808	게임 (IOI13_game)	C++17	100 / 100	2664 ms	42900 KiB

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20