Submission #349775

#	Time	Username	Problem	Language	Result	Execution time	Memory
349775		tengiz05	Game (IOI13_game)	C++17	0 / 100	1 ms	364 KiB

game

#include "game.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 10;
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;
int X1,Y1,X2,Y2;
struct node{
	node *left, *right;
	ll ans;
	node *mySeg;
	node(ll val){
		ans = val;
		left = right = NULL;
	}
};
node *MainRootYouKnow;
void init(int R, int C) {
	n = R, m = C;
	MainRootYouKnow = new node(0);
}

ll GetBy_Y_YouKnow(int l, int r, node *root){
	if(l > Y2 || r < Y1 || root == NULL)return 0;
	if(l >= Y1 && r <= Y2){
		return root->ans;
	}int mid = (l+r)>>1;
	return gcd2(GetBy_Y_YouKnow(l,mid,root->left),GetBy_Y_YouKnow(mid+1,r,root->right));
}

ll GetByWhatever(int l, int r, node *root){
	if(l > X2 || r < X1 || root == NULL)return 0;
	if(l >= X1 && r <= X2){
		if(root == NULL)return 0;
		return GetBy_Y_YouKnow(0,MAX,root->mySeg);
	}int mid = (l+r)>>1;
	return gcd2(GetByWhatever(l,mid,root->left),GetByWhatever(mid+1,r,root->right));	
}

ll get_in_range(int P, int Q, int U, int V) {
	X1=P,Y1=Q,X2=U,Y2=V;
	assert(X2 >= X1 && Y2 >= Y1);
	return GetByWhatever(0,MAX,MainRootYouKnow);
}

int X, Y, curl, curr; ll val;
ll Ans(node *t){
	if(t == NULL)return 0;
	return t->ans;
}
void UpdateByY(int l, int r, node *root){
	if(root == NULL)root = new node(0);
	if(l == r){
		if(curl == curr)root->ans = val;
		else root->ans = gcd2(get_in_range(curl, l, (curl+curr)/2, r), get_in_range((curl+curr+2)/2, l, curr, r));
		return;
	}int mid = (l+r)>>1;
	if(mid >= Y)UpdateByY(l,mid,root->left);
	else UpdateByY(mid+1,r,root->right);
	root->ans = gcd2(Ans(root->left), Ans(root->right));
}

void UpdateByX(int l, int r, node *root){
	if(root == NULL)root = new node(0);
	if(l == r){
		curl = l, curr = r;
		UpdateByY(0,MAX,root->mySeg);
		return;
	}int mid = (l+r)>>1;
	if(mid >= X)UpdateByX(l,mid,root->left);
	else UpdateByX(mid+1,r,root->right);
	curl = l, curr = r;
	UpdateByY(0,MAX,root->mySeg);
}

void update(int P, int Q, long long K) {
	X = P, Y = Q, val = K;
	UpdateByX(0,MAX,MainRootYouKnow);
}


ll calculate(int P, int Q, int U, int V) {
	//~ cout << "the initial array is:\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ X1=i,Y1=j,X2=i,Y2=j;
			//~ cout << GetByWhatever(0,MAX,MainRootYouKnow) << ' ';
		//~ }cout << '\n';
	//~ }cout << '\n';
	X1=P,Y1=Q,X2=U,Y2=V;
	return GetByWhatever(0,MAX,MainRootYouKnow);
}

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