Submission #798906

#	Time	Username	Problem	Language	Result	Execution time	Memory
798906		QwertyPi	Game (IOI13_game)	C++14	63 / 100	1276 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

long long gcd2(long long X, long long Y) {
	return __gcd(X, Y);
}

struct y_node{
	long long a = 0;
	y_node *left = 0, *right = 0;
};

struct x_node{
	long long a = 0;
	x_node *left = 0, *right = 0;
	y_node y_tree;
};
int R, C;

long long get(y_node *v){
	if(!v) return 0;
	return v->a; 
}

long long get(x_node *v){
	if(!v) return 0;
	return v->a;
}

x_node root;
void update_y(int y, long long K, y_node *v, int y1 = 0, int y2 = C - 1){
	if(y1 == y2){
		v->a = K;
	}else{
		int ym = (y1 + y2) / 2;
		if(y <= ym){
			if(!v->left) v->left = new y_node();
			update_y(y, K, v->left, y1, ym);
		}else{
			if(!v->right) v->right = new y_node();
			update_y(y, K, v->right, ym + 1, y2);
		}
		v->a = gcd2(get(v->left), get(v->right));
	}
}

long long calc_y(int qy1, int qy2, y_node *v, int y1 = 0, int y2 = C - 1){
	if(!v || qy1 > y2 || y1 > qy2) return 0;
	if(qy1 <= y1 && y2 <= qy2) return v->a;
	int ym = (y1 + y2) / 2;
	long long a1 = 0, a2 = 0;
	if(v->left) a1 = calc_y(qy1, qy2, v->left, y1, ym);
	if(v->right) a2 = calc_y(qy1, qy2, v->right, ym + 1, y2);
	return gcd2(a1, a2);
}

void update_x(int x, int y, long long K, x_node *v, int x1 = 0, int x2 = R - 1){
	if(x1 == x2){
		update_y(y, K, &v->y_tree);
		return;
	}
	int xm = (x1 + x2) / 2;
	if(x <= xm){
		if(!v->left) v->left = new x_node();
		update_x(x, y, K, v->left, x1, xm);
	}else{
		if(!v->right) v->right = new x_node();
		update_x(x, y, K, v->right, xm + 1, x2);
	}
	long long A = gcd2(v->left ? calc_y(y, y, &v->left->y_tree) : 0, 
					   v->right ? calc_y(y, y, &v->right->y_tree) : 0);
	update_y(y, A, &v->y_tree);
}

long long calc_x(int qx1, int qx2, int qy1, int qy2, x_node *v, int x1 = 0, int x2 = R - 1){
	if(!v || qx1 > x2 || x1 > qx2) return 0;
	if(qx1 <= x1 && x2 <= qx2) return calc_y(qy1, qy2, &v->y_tree);
	int xm = (x1 + x2) / 2;
	long long a1 = 0, a2 = 0;
	if(v->left) a1 = calc_x(qx1, qx2, qy1, qy2, v->left, x1, xm);
	if(v->right) a2 = calc_x(qx1, qx2, qy1, qy2, v->right, xm + 1, x2);
	return gcd2(a1, a2);
}

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

void update(int P, int Q, long long K) {
    update_x(P, Q, K, &root);
}

long long calculate(int P, int Q, int U, int V) {
    return calc_x(P, U, Q, V, &root);
}

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