Submission #1013217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013217		AmirAli_H1	Game (IOI13_game)	C++17	10 / 100	13090 ms	9932 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());

const int sq = 150;
const int maxn = sq * sq;
const int maxlg = 15;
vector<int> arr1, arr2;
vector<pair<pll, ll>> A;
vector<pll> Ax[maxn], Asq[sq];
int indx[maxn], indsq[maxn];
ll Rx[maxn][maxlg], Rsq[maxn][maxlg];

int GI1(int x) {
	return lower_bound(all(arr1), x) - arr1.begin();
}
int GI2(int x) {
	return lower_bound(all(arr2), x) - arr2.begin();
}

int Gx(int i, int r) {
	return indx[r] + i;
}
int Gsq(int i, int r) {
	return indsq[r] + i;
}

void addx(int R) {
	for (int x : arr1) {
		if (R == x) return ;
	}
	arr1.pb(R); int j = len(arr1) - 1;
	while (j - 1 >= 0 && arr1[j] < arr1[j - 1]) {
		swap(arr1[j], arr1[j - 1]); j--;
	}
}

void add_val(pair<pll, ll> R) {
	int j = 0;
	for (auto f : A) {
		if (R.F == f.F) {
			A[j].S = R.S;
			return ;
		}
		j++;
	}
	A.pb(R); j = len(A) - 1;
	while (j - 1 >= 0 && A[j] < A[j - 1]) {
		swap(A[j], A[j - 1]); j--;
	}
}

void init(int R, int C) {
	return ;
}

void calx(int ind) {
	int n = len(Ax[ind]);
	for (int i = n - 1; i >= 0; i--) {
		Rx[Gx(i, ind)][0] = Ax[ind][i].S;
		for (int j = 1; j < maxlg; j++) {
			int k = i + (1 << (j - 1));
			if (k >= n) break;
			Rx[Gx(i, ind)][j] = __gcd(Rx[Gx(i, ind)][j - 1], Rx[Gx(k, ind)][j - 1]);
		}
	}
}

void calsq(int ind) {
	int n = len(Asq[ind]);
	for (int i = n - 1; i >= 0; i--) {
		Rsq[Gsq(i, ind)][0] = Asq[ind][i].S;
		for (int j = 1; j < maxlg; j++) {
			int k = i + (1 << (j - 1));
			if (k >= n) break;
			Rsq[Gsq(i, ind)][j] = __gcd(Rsq[Gsq(i, ind)][j - 1], Rsq[Gsq(k, ind)][j - 1]);
		}
	}
}

void update(int i, int j, ll x) {
	addx(i); swap(arr1, arr2); addx(j); swap(arr1, arr2);
	add_val(Mp(Mp(i, j), x));
	for (int i = 0; i < len(arr2); i++) Ax[i].clear();
	for (int i = 0; i < len(arr2); i += sq) Asq[i / sq].clear();
	for (auto f : A) {
		int i = GI1(f.F.F), j = GI2(f.F.S); ll x = f.S;
		Ax[j].pb(Mp(i, x));
		Asq[j / sq].pb(Mp(i, x));
	}
	for (int i = 0; i < len(arr2); i++) {
		if (i == 0) indx[i] = 0;
		else indx[i] = len(Ax[i - 1]) + indx[i - 1];
		calx(i);
	}
	for (int i = 0; i < len(arr2); i += sq) {
		if (i == 0) indsq[i] = 0;
		else indsq[i] = len(Asq[i - 1]) + indsq[i - 1];
		calsq(i / sq);
	}
}

ll get_val(int ind, int l, int r) {
	l = lower_bound(all(Ax[ind]), (pll) Mp(l, -1)) - Ax[ind].begin();
	r = lower_bound(all(Ax[ind]), (pll) Mp(r, -1)) - Ax[ind].begin();
	if (r - l <= 0) return 0;
	int j = __lg(r - l);
	return __gcd(Rx[Gx(l, ind)][j], Rx[Gx(r - (1 << j), ind)][j]);
}

ll get_valx(int ind, int l, int r) {
	l = lower_bound(all(Asq[ind]), (pll) Mp(l, -1)) - Asq[ind].begin();
	r = lower_bound(all(Asq[ind]), (pll) Mp(r, -1)) - Asq[ind].begin();
	if (r - l <= 0) return 0;
	int j = __lg(r - l);
	return __gcd(Rsq[Gsq(l, ind)][j], Rsq[Gsq(r - (1 << j), ind)][j]);
}

ll calculate(int l1, int l2, int r1, int r2) {
	r1++; r2++;
	l1 = GI1(l1); r1 = GI1(r1);
	l2 = GI2(l2); r2 = GI2(r2);
	ll res = 0;
	if (r2 - l2 <= 2 * sq) {
		for (int i = l2; i < r2; i++) {
			res = __gcd(res, get_val(i, l1, r1));
		}
	}
	else {
		int lx = (l2 / sq) + (l2 % sq != 0), rx = r2 / sq;
		for (int i = l2; i < lx; i++) {
			res = __gcd(res, get_val(i, l1, r1));
		}
		for (int i = lx; i < rx; i += sq) {
			res = __gcd(res, get_valx(i / sq, l1, r1));
		}
		for (int i = rx; i < r2; i++) {
			res = __gcd(res, get_val(i, l1, r1));
		}
	}
	return res;
}

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