Submission #1014966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014966		AmirAli_H1	Game (IOI13_game)	C++17	80 / 100	2663 ms	256000 KiB

game

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
const int maxs = 1e7 + 4;
ll t[maxs]; int tx[maxs];
int lc[maxs], rc[maxs], sz;

void set_val(int v, int u1, int u2, int tl, int tr, int i, int j, ll x) {
	if (tr - tl == 1) {
		if (tx[v] == -1) {
			t[v] = 0;
			if (u1 == -1 && u2 == -1) t[v] = x;
			else {
				if (u1 != -1) t[v] = __gcd(t[v], t[u1]);
				if (u2 != -1) t[v] = __gcd(t[v], t[u2]);
			}	
		}
		else {
			set_val(tx[v], -1, -1, 0, m, j, -1, x);
		}
		return ;
	}
	
	int mid = (tl + tr) / 2;
	if (i < mid) {
		if (lc[v] == -1) {
			int u = sz++; lc[v] = u;
			if (tx[v] != -1) tx[u] = sz++;
		}
		int x1 = u1, x2 = u2;
		if (x1 != -1) x1 = lc[x1];
		if (x2 != -1) x2 = lc[x2];
		set_val(lc[v], x1, x2, tl, mid, i, j, x);
	}
	else {
		if (rc[v] == -1) {
			int u = sz++; rc[v] = u;
			if (tx[v] != -1) tx[u] = sz++;
		}
		int x1 = u1, x2 = u2;
		if (x1 != -1) x1 = rc[x1];
		if (x2 != -1) x2 = rc[x2];
		set_val(rc[v], x1, x2, mid, tr, i, j, x);
	}
	
	t[v] = 0;
	if (tx[v] == -1) {
		if (lc[v] != -1) t[v] = __gcd(t[v], t[lc[v]]);
		if (rc[v] != -1) t[v] = __gcd(t[v], t[rc[v]]);
	}
	else {
		int x1 = -1, x2 = -1;
		if (lc[v] != -1) x1 = tx[lc[v]];
		if (rc[v] != -1) x2 = tx[rc[v]];
		set_val(tx[v], x1, x2, 0, m, j, -1, x);
	}
}

ll get_val(int v, int tl, int tr, int l, int r, int lx, int rx) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return 0;
	if (l == tl && r == tr) {
		if (tx[v] != -1) {
			return get_val(tx[v], 0, m, lx, rx, -1, -1);
		}
		else return t[v];
	}
	
	ll res = 0; int mid = (tl + tr) / 2;
	if (lc[v] != -1) res = __gcd(res, get_val(lc[v], tl, mid, l, r, lx, rx));
	if (rc[v] != -1) res = __gcd(res, get_val(rc[v], mid, tr, l, r, lx, rx));
	return res;
}

void init(int R, int C) {
	n = R; m = C;
	fill(tx, tx + maxs, -1);
	fill(lc, lc + maxs, -1); fill(rc, rc + maxs, -1);
	sz = 1; tx[0] = sz++;
	return ;
}

void update(int i, int j, ll x) {
	set_val(0, -1, -1, 0, n, i, j, x);
}

ll calculate(int l1, int l2, int r1, int r2) {
	r1++; r2++;
	return get_val(0, 0, n, l1, r1, l2, r2);
}

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