Submission #765421

#	Time	Username	Problem	Language	Result	Execution time	Memory
765421		alex_2008	Game (IOI13_game)	C++14	100 / 100	3486 ms	189620 KiB

game

#include "game.h"

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

struct updateVal
{
	int R;
	int C;
	ll V;
};

const ll W = 1200000, WW = 13000000;
ll value[WW];
int updateIndex[WW]; // index in array updates

vector<updateVal> updates;

int ls[WW], rs[WW], lsy[W], rsy[W], root[W];
int sz = 2, sz2 = 2, Root = 1;
int n, m;
ll qans;

ll gcd(ll a, ll b) {
	while (a && b) {
		(a > b) ? a %= b : b %= a;
	}
	return a + b;
}
void queryX(int &v, int C1, int C2, int vleft, int vright) {
	if (vright < C1 || vleft > C2) return;
	if (vleft >= C1 && vright <= C2) {
		qans = gcd(qans, value[v]);
		return;
	}
	if (ls[v] == 0 && rs[v] == 0) {
		qans = gcd(qans, value[v]);
		return;
	}
	int mid = (vleft + vright) / 2;
	queryX(ls[v], C1, C2, vleft, mid);
	queryX(rs[v], C1, C2, mid + 1, vright);
}

void queryXWithCheck(int v, int C) {
	if (updateIndex[v] != -1) {
		if (updates[updateIndex[v]].C == C)
			qans = gcd(qans, updates[updateIndex[v]].V);
	}
	else {
		queryX(root[v], C, C, 1, m);
	}
}
void queryY(int &v, int R1, int C1, int R2, int C2, int vleft, int vright) {
	if (v == 0) return;
	if (vleft > R2 || vright < R1) {
		return;
	}
	
	if (updateIndex[v] != -1) {
		if (updates[updateIndex[v]].R >= R1 && updates[updateIndex[v]].R <= R2 &&
			updates[updateIndex[v]].C >= C1 && updates[updateIndex[v]].C <= C2)
			qans = gcd(qans, updates[updateIndex[v]].V);
		return;
	}
	if (vleft >= R1 && vright <= R2) {
		queryX(root[v], C1, C2, 1, m);
		return;
	}
	
	int mid = (vleft + vright) / 2;
	queryY(lsy[v], R1, C1, R2, C2, vleft, mid);
	queryY(rsy[v], R1, C1, R2, C2, mid + 1, vright);
}
void Updatex(int &v, int C, ll val, int vleft, int vright) {	
	if (vleft > C || vright < C) return;
	if (v == 0) v = ++sz;
	if (vleft == vright) {
		value[v] = val;
		return;
	}
	int mid = (vleft + vright) / 2;
	if (C <= mid) Updatex(ls[v], C, val, vleft, mid);
	else Updatex(rs[v], C, val, mid + 1, vright);
	value[v] = 0;
	if (ls[v]) value[v] = gcd(value[v], value[ls[v]]);
	if (rs[v]) value[v] = gcd(value[v], value[rs[v]]);
	return;
}
void Updatey(int &v, int R, int C, ll val, int vleft, int vright) {
	if (vleft > R || vright < R) return;
	if (v == 0) {
		v = ++sz2;
	}
	if (vleft == vright) {
		Updatex(root[v], C, val, 1, m);
		return;
	}
	if (updateIndex[v] == -1 && lsy[v] == 0 && rsy[v] == 0) {
		updates.push_back({ R, C, val });
		updateIndex[v] = updates.size() - 1;
		return;
	}
	int mid = (vleft + vright) / 2;
	if (updateIndex[v] != -1) {
		if (updates[updateIndex[v]].R <= mid)
		{
			Updatey(lsy[v], updates[updateIndex[v]].R,
				updates[updateIndex[v]].C, updates[updateIndex[v]].V,
				vleft, mid);
		}
		else {
			Updatey(rsy[v], updates[updateIndex[v]].R,
				updates[updateIndex[v]].C, updates[updateIndex[v]].V,
				mid + 1, vright);
		}
		
		qans = 0;
		if (lsy[v]) {
			queryXWithCheck(lsy[v], updates[updateIndex[v]].C);
		}
		if (rsy[v]) {
			queryXWithCheck(rsy[v], updates[updateIndex[v]].C);
		}
		Updatex(root[v], updates[updateIndex[v]].C, qans, 1, m);
		updateIndex[v] = -1;
	}
	if (R <= mid)
	{
		Updatey(lsy[v], R, C, val, vleft, mid);
	}
	else
	{
		Updatey(rsy[v], R, C, val, mid + 1, vright);
	}

	qans = 0;
	if (lsy[v]) {
		queryXWithCheck(lsy[v], C);
	}
	if (rsy[v]) {
		queryXWithCheck(rsy[v], C);
	}
	Updatex(root[v], C, qans, 1, m);
}
void init(int R, int C) {
	n = R;
	m = C;
	Root = 1;
	for (int i = 0; i < WW; ++i)
		updateIndex[i] = -1;
}
void update(int R, int Q, long long K) {
	Updatey(Root, R + 1, Q + 1, K, 1, n);
}
long long calculate(int P, int Q, int U, int V) {
	qans = 0;
	queryY(Root, P + 1, Q + 1, U + 1, V + 1, 1, n);
	return qans;
}

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