제출 #707265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707265		Nonoze	게임 (IOI13_game)	C++14	37 / 100	13069 ms	28236 KiB

game

#include "game.h"
#include <bits/stdc++.h>
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 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;

#undef int
void init(int R, int C) {
	#define int long long
	st.resize(R);
	int size=1;
	while (size < C) size*=2;
	for (int i = 0; i < R; ++i) st[i].init(size);
	#undef int
}
 
void update(int P, int Q, long long K) {
	#define int long long
	st[P].set(Q, K);
	#undef int
}
 
long long calculate(int P, int Q, int U, int V) {
	#define int long long
	int ans=0;
	for (int i = P; i <= U; ++i)
	{
		ans=gcd2(ans, st[i].calc(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