Submission #351262

#	Time	Username	Problem	Language	Result	Execution time	Memory
351262		Mefarnis	Game (IOI13_game)	C++14	37 / 100	13090 ms	103024 KiB

game

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

struct Quad {
	LL val;
	Quad* child[2][2];
	Quad() {
		val = 0;
		child[0][0] = NULL;
		child[0][1] = NULL;
		child[1][0] = NULL;
		child[1][1] = NULL;
	}
}*root;

LL gcd(LL x, LL y) {
    if(!y)
    	return x;
    return gcd(y,x%y);
}

int n,m;

void init(int xl , int xr , int yl , int yr , Quad* node) {
	if(xl == xr && yl == yr)
		return;
	int xm = (xl+xr)>>1;
	int ym = (yl+yr)>>1;
	if(xl == xr) {
		node->child[0][0] = new Quad();
		init(xl,xm,yl,ym,node->child[0][0]);
		node->child[0][1] = new Quad();
		init(xl,xm,ym+1,yr,node->child[0][1]);
	}
	else if(yl == yr) {
		node->child[0][0] = new Quad();
		init(xl,xm,yl,ym,node->child[0][0]);
		node->child[1][0] = new Quad();
		init(xm+1,xr,yl,ym,node->child[1][0]);
	}
	else {
		node->child[0][0] = new Quad();
		init(xl,xm,yl,ym,node->child[0][0]);
		node->child[0][1] = new Quad();
		init(xl,xm,ym+1,yr,node->child[0][1]);
		node->child[1][0] = new Quad();
		init(xm+1,xr,yl,ym,node->child[1][0]);
		node->child[1][1] = new Quad();
		init(xm+1,xr,ym+1,yr,node->child[1][1]);
	}
}

void init(int R, int C) {
	n = R;
	m = C;
	root = new Quad();
	init(0,n-1,0,m-1,root);
}

LL update(int xl , int xr , int yl , int yr , int X , int Y , LL VAL , Quad* node) {
	if(xr < X || X < xl)
		return node->val;
	if(yr < Y || Y < yl)
		return node->val;
	if(xl == xr && yl == yr)
		return node->val = VAL;
	LL GCD = 0;
	int xm = (xl+xr)>>1;
	int ym = (yl+yr)>>1;
	if(xl == xr) {
		GCD = gcd(GCD, update(xl,xm,yl,ym,X,Y,VAL,node->child[0][0]));
		GCD = gcd(GCD, update(xl,xm,ym+1,yr,X,Y,VAL,node->child[0][1]));
	}
	else if(yl == yr) {
		GCD = gcd(GCD, update(xl,xm,yl,ym,X,Y,VAL,node->child[0][0]));
		GCD = gcd(GCD, update(xm+1,xr,yl,ym,X,Y,VAL,node->child[1][0]));
	}
	else {
		GCD = gcd(GCD, update(xl,xm,yl,ym,X,Y,VAL,node->child[0][0]));
		GCD = gcd(GCD, update(xl,xm,ym+1,yr,X,Y,VAL,node->child[0][1]));
		GCD = gcd(GCD, update(xm+1,xr,yl,ym,X,Y,VAL,node->child[1][0]));
		GCD = gcd(GCD, update(xm+1,xr,ym+1,yr,X,Y,VAL,node->child[1][1]));
	}
	return node->val = GCD;
}

void update(int P, int Q, LL K) {
    update(0,n-1,0,m-1,P,Q,K,root);
}

LL query(int xl , int xr , int yl , int yr , int X1 , int Y1 , int X2 , int Y2 , Quad* node) {
	if(xr < X1 || X2 < xl)
		return 0;
	if(yr < Y1 || Y2 < yl)
		return 0;
	if(X1 <= xl && xr <= X2 && Y1 <= yl && yr <= Y2)
		return node->val;
	LL GCD = 0;
	int xm = (xl+xr)>>1;
	int ym = (yl+yr)>>1;
	if(xl == xr) {
		GCD = gcd(GCD, query(xl,xm,yl,ym,X1,Y1,X2,Y2,node->child[0][0]));
		GCD = gcd(GCD, query(xl,xm,ym+1,yr,X1,Y1,X2,Y2,node->child[0][1]));
	}
	else if(yl == yr) {
		GCD = gcd(GCD, query(xl,xm,yl,ym,X1,Y1,X2,Y2,node->child[0][0]));
		GCD = gcd(GCD, query(xm+1,xr,yl,ym,X1,Y1,X2,Y2,node->child[1][0]));
	}
	else {
		GCD = gcd(GCD, query(xl,xm,yl,ym,X1,Y1,X2,Y2,node->child[0][0]));
		GCD = gcd(GCD, query(xl,xm,ym+1,yr,X1,Y1,X2,Y2,node->child[0][1]));
		GCD = gcd(GCD, query(xm+1,xr,yl,ym,X1,Y1,X2,Y2,node->child[1][0]));
		GCD = gcd(GCD, query(xm+1,xr,ym+1,yr,X1,Y1,X2,Y2,node->child[1][1]));
	}
	return GCD;
}

LL calculate(int P, int Q, int U, int V) {
    return query(0,n-1,0,m-1,P,Q,U,V,root);
}

/*
int main() {
	init(2,3);
	update(0,0,20);
	update(0,2,15);
	update(1,1,12);
	printf("%lld\n",calculate(0,0,0,2));
	printf("%lld\n",calculate(0,0,1,1));
	update(0,1,6);
	update(1,1,14);
	printf("%lld\n",calculate(0,0,0,2));
	printf("%lld\n",calculate(0,0,1,1));
	return 0;
}
*/

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