Submission #788826

#	Time	Username	Problem	Language	Result	Execution time	Memory
788826		Ludissey	Game (IOI13_game)	C++14	37 / 100	13109 ms	71320 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;

int query(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(root->left, left, mid, qLeft, qRight), query(root->right, mid + 1, right, qLeft, qRight));
}

void update_(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_(root->left, left, mid, point, nValue);

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

	root->updates();
}

void build(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(root->left, left, mid);
	build(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;
	roots.resize(r);
	for (int i = 0; i < r; i++)
	{
		roots[i] = new node{ NULL, NULL, 0 };
		build(roots[i], 0, c - 1);
	}
	vector<node*> rootasd=roots;
	return;
}

void update(signed P, signed Q, long long K) {
	update_(roots[P], 0, c - 1, Q, K);
}


long long calculate(signed P, signed Q, signed U, signed V) {
	int gcd = 0;
	for (int i = P; i <= U; i++)
	{
		gcd = gcd2(query(roots[i], 0, c - 1, Q, V), gcd);
	}
	return gcd;
}

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