Submission #1263747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263747		aren_dance	Game (IOI13_game)	C++20	10 / 100	13095 ms	321536 KiB

game

#include <bits/stdc++.h>
#define ll long long
#include "game.h"
using namespace std;
vector<vector<vector<ll>>> a;
vector<vector<ll>> b;
ll gcd(ll x,ll y) {
	if (x > y) {
		swap(x, y);
	}
	if (x == 0) {
		return y;
	}
	if (y % x == 0) {
		return x;
	}
	return gcd(y%x,x);
}
void init(int R, int C) {
	a.resize(R);
	b.resize(R);
	for (int i = 0;i < R;++i) {
		a[i].resize(C);
		b[i].resize(C);
		for (int j = 0;j < C;++j) {
			b[i][j] = 0;
			a[i][j].resize(20);
			for (int k = 0;k < 20;++k) {
				a[i][j][k] = 0;
			}
		}
	}
}
void update(int P, int Q, long long K) {
	b[P][Q] = K;
	a[P][Q][0] = K;
	for (int j = 1;j < 20;++j) {
		for (int i = 0;i < a[P].size();++i) {
			a[P][i][j] = gcd(a[P][i][j-1],a[P][min(i+(1<<(j-1)),int(a[P].size()) - 1)][j - 1]);
		}
	}
}
long long calculate(int P, int Q, int U, int V) {
	ll answ = 0;
	for (int i = P;i <= U;++i) {
		ll x = log2(V-Q+1);
		answ = gcd(answ, gcd(a[i][Q][x],a[i][V-(1<<x)+1][x]));
	}
	return answ;
}

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