Submission #281803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281803	2020-08-23T13:44:19 Z	Saboon	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int n = 22000;
const int SQ = 150;

int numBlock;
vector<pair<pair<int,int>,ll>> a[SQ];

ll gcd2(ll X, ll Y){
    ll tmp;
    while (X != Y && Y != 0){
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct node{
	node *lc = nullptr;
	node *rc = nullptr;
	ll GCD = 0;
	node *getlc(){
		if (this->lc == NULL)
			this->lc = new node();
		return this->lc;
	}
	node *getrc(){
		if (this->rc == NULL)
			this->rc = new node();
		return this->rc;
	}
	void change(int L, int R, int idx, ll val){
		if (idx < L or R <= idx)
			return;
		if (L+1 == R){
			GCD = val;
			return;
		}
		int mid = (L + R) >> 1;
		this->getlc()->change(L, mid, idx, val);
		this->getrc()->change(mid, R, idx, val);
	}
	ll get(int L, int R, int l, int r){
		if (r <= L or R <= l)
			return 0;
		if (l <= L and R <= r)
			return GCD;
		int mid = (L + R) >> 1;
		if (lc == nullptr)
			return 0;
		return gcd(getlc()->get(L, mid, l, r), getrc()->get(mid, R, l, r));
	}
};

node* root[SQ];

map<pair<int,int>, ll> mp;

void init(int R, int C){
	for (int i = 0; i < SQ; i++)
		a[i].clear();
	int n = mp.size();
	numBlock = max((n+SQ-1)/SQ,1);
	if (n == 0)
		root[0] = new node;
	int idx = -1;
	for (auto it : mp){
		idx ++;
		if (idx % SQ == 0)
			root[idx/SQ] = new node;
		a[idx/SQ].push_back(it);
		root[idx/SQ]->change(0, 1e9, it.first.second, it.second);
	}
}

void update(int P, int Q, ll K){
	mp[{P,Q}] = K;
	int block = numBlock-1;
	for (int i = 1; i < numBlock; i++)
		if (P <= a[i][0].first.first)
			block = i-1;
	a[block].push_back({{P,Q},K});
	if (a[block].size() == 2*SQ)
		init(0,0);
	else
		root[block]->change(0, 1e9, Q, K);
}

ll calculate(int P, int Q, int U, int V){
	if (P > U)
		swap(P, U);
	if (Q > V)
		swap(Q, V);
	ll answer = 0;
	for (int i = 0; i < numBlock; i++){
		if (a[i][0].first.first > U)
			break;
		if (a[i].back().first.first < P)
			continue;
		if (a[i][0].first.first >= P and a[i].back().first.first <= U){
			answer = gcd2(answer, root[i]->get(0, 1e9, Q, V+1));
			continue;
		}
		for (auto it : a[i]){
			int p = it.first.first, q = it.first.second;
			ll x = it.second;
			if (P <= p and p <= U and Q <= q and q <= V)
				answer = gcd2(answer, x);
		}
	}
	return answer;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~
game.cpp: In member function 'll node::get(int, int, int, int)':
game.cpp:54:10: error: 'gcd' was not declared in this scope; did you mean 'gcd2'?
   54 |   return gcd(getlc()->get(L, mid, l, r), getrc()->get(mid, R, l, r));
      |          ^~~
      |          gcd2