oj.uz

Submission #349775

# Submission time Handle Problem Language Result Execution time Memory
349775 2021-01-18T11:12:23 Z tengiz05 Game (IOI13_game) C++17
0 / 100
 1 ms 364 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -