Submission #298142

#	Time	Username	Problem	Language	Result	Execution time	Memory
298142		williamMBDK	Game (IOI13_game)	C++11	37 / 100	13096 ms	40376 KiB

game

#include<bits/stdc++.h>
#include "game.h"
#define int long long
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 ST{
	vector<int> arr;
	ST(){}
	ST(int N){
		arr = vector<int> (4 * N);
	}
	int u(int idx, int l, int r, int qidx, int qval){
		if(r < qidx || l > qidx) return arr[idx];
		if(l == r && qidx == l){
			arr[idx] = qval;
			return arr[idx];
		}
		int m = (l + r) / 2;
		arr[idx] = gcd2(u(idx * 2, l, m, qidx, qval), u(idx * 2 + 1, m + 1, r, qidx, qval));
		// cout << arr[idx] << " " << l << " " << r << endl;
		return arr[idx];
	}	
	int q(int idx, int l, int r, int ql, int qr){
		if(l > qr || r < ql) return 0;
		if(l >= ql && r <= qr) return arr[idx];
		int m = (l + r) / 2;
		return gcd2(q(idx * 2, l, m, ql, qr), q(idx * 2 + 1, m + 1, r, ql, qr));
	}
};

int R, C;
vector<ST> sts;

void init(signed _R, signed _C) {
	R = _R;
	C = _C;
	sts = vector<ST> (R, ST(C));
}

void update(signed P, signed Q, int K) {
	sts[P].u(1,0,C-1,Q,K);
}

long long calculate(signed P, signed Q, signed U, signed V) {
	int res = 0;
	for(int i = P; i <= U; i++){
		res = gcd2(res, sts[i].q(1,0,C-1,Q,V));
	}
	return res;
}

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