Submission #349823

#	Time	Username	Problem	Language	Result	Execution time	Memory
349823		tengiz05	Game (IOI13_game)	C++17	63 / 100	2776 ms	256004 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 = (1<<30)-1;
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 snode{
	snode *left, *right;
	ll ans;
	snode(ll val){
		ans = val;
		left = right = NULL;
	}
};
struct node{
	node *left, *right;
	snode *mySeg;
	node(){
		left = right = NULL;
		mySeg = NULL;
	}
};


node *MainRootYouKnow;
void init(int R, int C) {
	n = R, m = C;
	MainRootYouKnow = new node();
	return;
}
ll GetBy_Y(int l, int r, snode *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(l,mid,root->left),GetBy_Y(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){
		return GetBy_Y(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(snode *t){
	if(t == NULL)return 0;
	return t->ans;
}
void UpdateByY(int l, int r, snode *root){
	if(l == r){
		int md = (curl+curr)/2;
		if(curl == curr)root->ans = val;
		else root->ans = gcd2(get_in_range(curl, l, md, r), get_in_range(md+1, l, curr, r));
	}else {
		int mid = (l+r)>>1;
		if(mid >= Y){
			if(root->left == NULL)root->left = new snode(0);
			UpdateByY(l,mid,root->left);
		}else {
			if(root->right == NULL)root->right = new snode(0);
			UpdateByY(mid+1,r,root->right);
		}root->ans = gcd2(Ans(root->left), Ans(root->right));
	}return;
}

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

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


ll calculate(int P, int Q, int U, int V) {
	return get_in_range(P,Q,U,V);
}

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