Submission #773996

#	Time	Username	Problem	Language	Result	Execution time	Memory
773996		Ludissey	Game (IOI13_game)	C++14	10 / 100	13094 ms	64720 KiB

game

#include "game.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>

const int MAX_C = 100000;
const int MAX_R = 100;

int r, c;

using namespace std;
#define int long long

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

struct node {
	node* left, * right;
	int gcd;

	void updates() {
		gcd = gcd2(left->gcd, right->gcd);
	}
};
vector<node*> roots;
node* ori_root;

int query_ver(node* root, int left, int right, int qLeft, int qRight) {
	if (left > qRight || right < qLeft) return 0;
	if (left >= qLeft && right <= qRight) return root->gcd;

	int mid = (left + right) / 2;
	return gcd2(query_ver(root->left, left, mid, qLeft, qRight), query_ver(root->right, mid + 1, right, qLeft, qRight));
}

void update_ver(node* root, int left, int right, int point, int nValue) {
	int qLeft, qRight;
	qLeft = qRight = point;
	if (left > qRight || right < qLeft) return;

	if (left >= qLeft && right <= qRight) {
		root->gcd = nValue;
		return;
	}

	int mid = (left + right) / 2;
	update_ver(root->left, left, mid, point, nValue);

	update_ver(root->right, mid + 1, right, point, nValue);

	root->updates();
}

void build_ver(node* root, int left, int right) {
	if (left == right) {
		root->gcd = 0;
		return;
	}
	int mid = (left + right) / 2;

	root->left = new node{ NULL, NULL, 0 };
	root->right = new node{ NULL, NULL, 0 };

	build_ver(root->left, left, mid);
	build_ver(root->right, mid + 1, right);

	root->updates();
}

int query_hor(node* root, int left, int right, int qLeft, int qRight, int qDown, int qUp) {
	if (left > qRight || right < qLeft) return 0;
	if (left == right) {
		return query_ver(root, 0, r-1, qDown, qUp);
	}

	int mid = (left + right) / 2;
	return gcd2(query_hor(root->left, left, mid, qLeft, qRight, qDown, qUp), query_hor(root->right, mid + 1, right, qLeft, qRight, qDown, qUp));
}

void update_hor(node* root, int left, int right, int hor_point, int ver_point, int nValue) {
	int qLeft, qRight;
	qLeft = qRight = hor_point;
	if (left > qRight || right < qLeft) return;

	if (left == right) {
		update_ver(root, 0, r - 1, ver_point, nValue);
		return;
	}

	int mid = (left + right) / 2;
	update_hor(root->left, left, mid, hor_point, ver_point, nValue);

	update_hor(root->right, mid + 1, right, hor_point, ver_point, nValue);

	root->updates();
}

void build_hor(node* root, int left, int right) {
	if (left == right) {
		build_ver(root, 0, r-1);
		return;
	}
	int mid = (left + right) / 2;

	root->left = new node{ NULL, NULL, 0 };
	root->right = new node{ NULL, NULL, 0 };

	build_hor(root->left, left, mid);
	build_hor(root->right, mid + 1, right);

	root->updates();
}

void destroy(node* root) {
	if (root->left) destroy(root->left);
	if (root->right) destroy(root->right);
	delete root;
}

void init(signed R, signed C) {
	r = R;
	c = C;
	ori_root = new node{ NULL,NULL,0 };
	build_hor(ori_root, 0, C - 1);
    return;
}

void update(signed P, signed Q, long long K) {
	update_hor(ori_root, 0, c - 1, Q, P, K);
}
    

long long calculate(signed P, signed Q, signed U, signed V) {
    int gcd = 0;
	gcd = query_hor(ori_root, 0, c - 1, Q, V, P, U);
    return gcd;
}

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