Submission #426153

#	Time	Username	Problem	Language	Result	Execution time	Memory
426153		frodakcin	Game (IOI13_game)	C++17	80 / 100	5104 ms	256000 KiB

game

#include "game.h"
#include <cstdio>

long long gcd(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

using ll = long long;

const int MU = 2.2e4+10;
const int MQ = 2.5e5+10;

const int M1 = 30 * 30 * MU / 2;
const int M2 = 30 * MU;

int R, C, X1, X2;
ll st1[M1]; int l1[M1], r1[M1];
int st2[M2], l2[M2], r2[M2], root;

void init(int R, int C) {
	::R=R, ::C=C;
}

void upd1(int& n, int l, int r, int Q, ll K)
{
	if(!n) n=++X1;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(Q<m) upd1(l1[n], l, m, Q, K);
		else upd1(r1[n], m, r, Q, K);
		st1[n]=gcd(st1[l1[n]], st1[r1[n]]);
	}
	else
		st1[n]=K;
}

void up(int& p, int a, int b, int l, int r, int Q)
{
	if(!p) p=++X1;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(Q<m) up(l1[p], l1[a], l1[b], l, m, Q);
		else up(r1[p], r1[a], r1[b], m, r, Q);
	}
	st1[p]=gcd(st1[a], st1[b]);
}

void upd2(int& n, int l, int r, int P, int Q, ll K)
{
	if(!n) n=++X2;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(P<m) upd2(l2[n], l, m, P, Q, K);
		else upd2(r2[n], m, r, P, Q, K);
		up(st2[n], st2[l2[n]], st2[r2[n]], 0, C, Q);
	}
	else
		upd1(st2[n], 0, C, Q, K);
}

void update(int P, int Q, long long K) {
	upd2(root, 0, R, P, Q, K);
}

ll qry1(int n, int l, int r, int Q, int V)
{
	if(!n) return 0;
	if(Q <= l && r <= V) return st1[n];
	else
	{
		int m=l+(r-l)/2;
		ll v=0;
		if(Q<m) v = gcd(v, qry1(l1[n], l, m, Q, V));
		if(m<V) v = gcd(v, qry1(r1[n], m, r, Q, V));
		return v;
	}
}

ll qry2(int n, int l, int r, int P, int U, int Q, int V)
{
	if(!n) return 0;
	if(P <= l && r <= U) return qry1(st2[n], 0, C, Q, V);
	else
	{
		int m=l+(r-l)/2;
		ll v=0;
		if(P<m) v = gcd(v, qry2(l2[n], l, m, P, U, Q, V));
		if(m<U) v = gcd(v, qry2(r2[n], m, r, P, U, Q, V));
		return v;
	}
}

long long calculate(int P, int Q, int U, int V) {
	return qry2(root, 0, R, P, U+1, Q, V+1);
}

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