Submission #514829

#	Time	Username	Problem	Language	Result	Execution time	Memory
514829		ritul_kr_singh	Game (IOI13_game)	C++17	100 / 100	3585 ms	233088 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
#define m ((l + r) / 2)
 
const int N = 6e5, M = 1.3e7, B = 25;
 
ll gcd2(ll X, ll Y) {
	while(X != Y && Y) swap(X %= Y, Y);
	return X;
}
 
int limRow, limCol, sL, sR; ll sV;
 
ll sGcd[M], xGcd[N*B];
int G[M], H[M], sCnt, xCnt, xP[N*B], xRow[N*B];
 
void sUpd(int l, int r, int u) {
	if(r - l < 2) return void(sGcd[u] = sV);
 
	sL<m? sUpd(l, m, G[u] ? : G[u] = ++sCnt):
		  sUpd(m, r, H[u] ? : H[u] = ++sCnt);
	sGcd[u] = gcd2(G[u] ? sGcd[G[u]] : 0LL, H[u] ? sGcd[H[u]] : 0LL);
}
 
ll sQry(int l, int r, int u) {
	if(sL<=l && r<=sR) return sGcd[u];
	if(sR<=l || r<=sL) return 0LL;
	return gcd2((G[u] ? sQry(l, m, G[u]) : 0LL),
				(H[u] ? sQry(m, r, H[u]) : 0LL));
}
 
void pointSet(int row, ll v, int &s) {
	if(s < 0) {	
		int i = -s, j = xP[i]; xP[i]++;
 
		for(int k=0; k+1<xP[i]; ++k) if(xRow[i+k] == row) {
			j = k; --xP[i];
			break;
		}
		xGcd[i+j] = v;
		xRow[i+j] = row;
 
		if(xP[i] == B) {
			s = ++sCnt;
 
			for(j=0; j<B; ++j)
				pointSet(xRow[i+j], xGcd[i+j], s);
		}
	} else sL = row, sV = v, sUpd(0, limRow, s);
}
 
ll rangeGcd(int l, int r, int &u) {
	if(u < 0) {
		int i = -u;
		ll res = 0;
		for(int j=0; j<xP[i]; ++j)
			if(l <= xRow[i+j] && xRow[i+j] < r)
				res = gcd2(res, xGcd[i+j]);
		return res;
	}
	sL = l, sR = r;
	return sQry(0, limRow, u);
}
 
int S[N], L[N], R[N], tL, tR, row, tCnt = 1;
ll currV;
 
void upd(int l, int r, int u) {
	if(!S[u]) (S[u] = --xCnt), xCnt -= B;
	if(r - l < 2) return pointSet(row, currV, S[u]);
 
	tL<m? upd(l, m, L[u] ? : L[u] = ++tCnt):
		  upd(m, r, R[u] ? : R[u] = ++tCnt);
 
	sV = gcd2(rangeGcd(row, row + 1, S[L[u]]),
			  rangeGcd(row, row + 1, S[R[u]]));
	pointSet(row, sV, S[u]);
}
 
ll query(int l, int r, int u) {
	if(tR<=l || r<=tL || !u || !S[u]) return 0LL;
	if(tL<=l && r<=tR) return rangeGcd(sL, sR, S[u]);
 
	return gcd2(query(l, m, L[u]), query(m, r, R[u]));
}
 
void init(int r, int c) { limCol = c, limRow = r; }
 
void update(int P, int Q, ll K) {
	row = P, tL = Q; currV = K;
	upd(0, limCol, 1);
}
 
ll calculate(int P, int Q, int U, int V) {
	sL = P, sR = U + 1;
	tL = Q, tR = V + 1;
    return query(0, limCol, 1);
}

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