Submission #766580

#	Time	Username	Problem	Language	Result	Execution time	Memory
766580		Sohsoh84	Game (IOI13_game)	C++17	36 / 100	1401 ms	9044 KiB

game

#include "game.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
 
const ll MAXN1 = 1e6 + 10;
const ll MAXN2 = 2e7 + 10;
const ll INF = 1e9 + 1;
 
ll sg1[MAXN1], sg2[MAXN2], sz1, sz2, R, C;
int lc1[MAXN1], rc1[MAXN1], O[MAXN2];
 
inline int node2(int par, int side) {	
	int v = ++sz2;
	if (!par) {
		int l = 0, r = R;
		int u = v;
		while (l < r) {
			u = node2(u, 0);
			r = (l + r) >> 1;
		}

		return v;
	}

	if (O[par] == 0) {
		if (side == 0) O[par] = -1;
		else O[par] = -2;
		
		return v;
	}
 
	if (O[par] == -1) return O[par] = (v << 1);
	else O[par] = (v << 1 | 1);
	return v;
}
 
inline int lc2(int v) {
	if (O[v] == 0 || O[v] == -2) return 0;
	if (O[v] == -1 || (O[v] >= 0 && (O[v] % 2) == 0)) return v + 1;
	return O[v] >> 1;
}
 
inline int rc2(int v) {
	if (O[v] == 0 || O[v] == -1) return 0;
	if (O[v] == -2 || (O[v] >= 0 && (O[v] % 2) == 1)) return v + 1;
	return O[v] >> 1;
}
 
inline int node1() {
	int v = ++sz1;
	sg1[v] = node2(0, 0);
	return v;
}
 
void update2_line(int y, ll val, int v, int bl2, int br2) {
	if (bl2 == br2) {
		sg2[v] = val;		
		return;
	}
 
	int mid = (bl2 + br2) >> 1;
	if (y <= mid) {
		if (!lc2(v)) node2(v, 0);
		update2_line(y, val, lc2(v), bl2, mid);
	} else {
		if (!rc2(v)) node2(v, 1);
		update2_line(y, val, rc2(v), mid + 1, br2);
	}
 
	sg2[v] = gcd(sg2[lc2(v)], sg2[rc2(v)]); // optimize
}
 
void update2_seg(int y, ll val, int v, int par_l, int par_r, int bl2, int br2) {
	sg2[v] = gcd(sg2[par_l], sg2[par_r]);
	if (bl2 == br2) return;
 
	int mid = (bl2 + br2) >> 1;
	if (y <= mid) {
		if (!lc2(v)) node2(v, 0);
		update2_seg(y, val, lc2(v), lc2(par_l), lc2(par_r), bl2, mid);
	} else {
		if (!rc2(v)) node2(v, 1);
		update2_seg(y, val, rc2(v), rc2(par_l), rc2(par_r), mid + 1, br2);
	}
 
}
 
void update1(int x, int y, ll val, int v, int bl1, int br1) {
	if (bl1 == br1) update2_line(y, val, sg1[v], 0, C);
	else {
		int mid = (bl1 + br1) >> 1;
		if (x <= mid) {
			if (!lc1[v]) lc1[v] = node1();
			update1(x, y, val, lc1[v], bl1, mid);
		} else {
			if (!rc1[v]) rc1[v] = node1();
			update1(x, y, val, rc1[v], mid + 1, br1);
		}
 
		update2_seg(y, val, sg1[v], sg1[lc1[v]], sg1[rc1[v]], 0, C);
	}
}
 
 
ll query2(int cl, int cr, int v, int bl2, int br2) {
	if (v == 0 || cl > br2 || cr < bl2) return 0;
	if (cl <= bl2 && cr >= br2) return sg2[v];
 
	int mid = (bl2 + br2) >> 1;
	return gcd(query2(cl, cr, lc2(v), bl2, mid), 
			query2(cl, cr, rc2(v), mid + 1, br2));
}
 
ll query1(int rl, int rr, int cl, int cr, int v, int bl1, int br1) {
	if (v == 0 || rl > br1 || rr < bl1) return 0; // optimize v == 0	
	if (rl <= bl1 && rr >= br1) {
		return query2(cl, cr, sg1[v], 0, C);
	}
 
	int mid = (bl1 + br1) >> 1;
	return gcd(query1(rl, rr, cl, cr, lc1[v], bl1, mid),
			query1(rl, rr, cl, cr, rc1[v], mid + 1, br1));
}
 
void init(int R_, int C_) {
	R = R_, C = C_;
	sg1[1] = node2(0, 0);
	sz1 = 1;
}
 
void update(int P, int Q, ll K) {
	update1(P, Q, K, 1, 0, R);
}
 
long long calculate(int P, int Q, int U, int V) {
	return query1(P, U, Q, V, 1, 0, R);
}

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