oj.uz

Submission #349816

# Submission time Handle Problem Language Result Execution time Memory
349816 2021-01-18T12:47:42 Z tengiz05 Game (IOI13_game) C++17
0 / 100
 4 ms 492 KB 
#include "game.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = (1<<2)-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 node{
	node *left, *right;
	ll ans;
	node *mySeg;
	node(ll val){
		ans = val;
		left = right = NULL;
		mySeg = NULL;
	}
};
node *MainRootYouKnow;
void init(int R, int C) {
	n = R, m = C;
	MainRootYouKnow = new node(0);
	return;
}
void extend(node *t){
	if(t == NULL)return;
	if(t->left == NULL)t->left = new node(0);
	if(t->right == NULL)t->right = new node(0);
}

ll GetBy_Y(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(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(node *t){
	if(t == NULL)return 0;
	return t->ans;
}
void UpdateByY(int l, int r, node *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 {
		extend(root);
		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));
	}return;
}

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

void update(int P, int Q, long long 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
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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