제출 #349646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349646		tengiz05	게임 (IOI13_game)	C++17	63 / 100	899 ms	256004 KiB

game

#include "game.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y) {
	ll tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
ll n, m;
vector<vector<ll>> t;
ll get(int x1, int y1, int x2, int y2){
	ll res = 0;
	for(x1+=n,x2+=n; x1<=x2; x1>>=1,x2>>=1){
		if(x1&1){
			for(int l=y1+m,r=y2+m; l<=r; l>>=1,r>>=1){
				if(l&1)res = gcd2(res, t[x1][l++]);
				if(!(r&1))res = gcd2(res, t[x1][r--]);
			}
			x1++;
		}if(!(x2&1)){
			for(int l=y1+m,r=y2+m; l<=r; l>>=1,r>>=1){
				if(l&1)res = gcd2(res, t[x2][l++]);
				if(!(r&1))res = gcd2(res, t[x2][r--]);
			}
			x2--;
		}
	}return res;
}

void upd(int x, int y, ll val){
	for(x+=n; x>=1; x>>=1){
		int i = y+m;
		for(; i>0; i>>=1){
			if(x>=n&&i>=m)t[x][i] = val;
			else if(i>=m)t[x][i] = gcd2(t[x<<1][i],t[x<<1|1][i]);
			t[x][i>>1] = gcd2(t[x][i], t[x][i^1]);
		}
	}
}

void init(int R, int C) {
	n = R, m = C;
	t.assign(n*2,vector<ll>(m*2,0));
}

void update(int P, int Q, long long K) {
	upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
	return get(P, Q, U, V);
}

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