Submission #707243

#	Time	Username	Problem	Language	Result	Execution time	Memory
707243		Nonoze	Game (IOI13_game)	C++14	0 / 100	1 ms	308 KiB

game

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

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 segtree
{
	int size;
	vector<int> values;

	void init(int n) {
		size=n;
		values.resize(2 * size + 2);
	}

	void set(int i, int v, int x, int qLeft, int qRight) {
		if (qLeft>=i && i>=qRight) {
			values[x]=v;
			return;
		}
		int mid = (qLeft + qRight) / 2;
		if (i>mid) {
			set(i, v, 2*x + 1, mid+1, qRight);
		} else {
			set(i, v, 2*x, qLeft, mid);
		}
		values[x]=gcd2(values[2*x], values[2*x + 1]);
	}

	void set(int i, int v) {
		set(i, v, 1, 0, size);
	}

	int calc(int left, int right, int x, int qLeft, int qRight) {
		if (qLeft > right || qRight < left) return 0;
		if (qLeft >= left && qRight <= right) return values[x];
		int mid = (qLeft + qRight) / 2;
		int s1 = calc(left, right, 2*x, qLeft, mid);
		int s2 = calc(left, right, 2*x + 1, mid+1, qRight);
		return gcd2(s1, s2);
	}

	int calc(int left, int right) {
		return calc(left, right, 1, 0, size);
	}
};

vector<segtree> st;

void init(int R, int C) {
	st.resize(R+1);
	int size=1;
	while (size < C) size*=2;
	for (int i = 0; i < R; ++i) st[i].init(size);
}

void update(int P, int Q, long long K) {
	st[P].set(Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	int ans=0;
	for (int i = P; i <= U; ++i)
	{
		ans=gcd2(ans, st[i].calc(Q, V));
	}
	return ans;
}

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