Submission #707260

#	Time	Username	Problem	Language	Result	Execution time	Memory
707260		Nonoze	Game (IOI13_game)	C++17	37 / 100	13088 ms	71416 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int R, C;

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=0;
	void update() {
		gcd=gcd2(left->gcd, right->gcd);
	}
};

vector<node*> st;

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


void updatest(node* root, int left, int right, int qLeft, int qRight, int nValue)
{
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight)
	{
		root->gcd=nValue;
		return;
	}

	int mid=(left+right)/2;
	updatest(root->left, left, mid, qLeft, qRight, nValue);
	updatest(root->right, mid+1, right, qLeft, qRight, nValue);
	root->update();
}

void build(node* root, int left, int right)
{
	if (left == right) {
		return;
	}

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

	int mid=(left+right)/2;
	build(root->left, left, mid);
	build(root->right, mid+1, right);
	root->update();
}
#undef int

void init(int A, int B) {
	#define int long long
	R=A, C=B;
	st.resize(R);
	for (int i = 0; i < R; ++i) {
		st[i]=new node{NULL, NULL, 0};
		build(st[i], 1, C);
	}
	#undef int
}

void update(int P, int Q, long long K) {
	#define int long long
	updatest(st[P], 1, C, Q+1, Q+1, K);
	#undef int
}

long long calculate(int P, int Q, int U, int V) {
	#define int long long
	int ans=0;
	Q++, V++;
	for (int i = P; i <= U; ++i)
	{
		ans=gcd2(ans, query(st[i], 1, C, Q, V));
	}
	return ans;
	#undef int
}

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