oj.uz

Submission #281804

# Submission time Handle Problem Language Result Execution time Memory
281804 2020-08-23T13:45:28 Z Saboon Game (IOI13_game) C++14
0 / 100
 1 ms 512 KB 
#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 gcd2(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;
      |      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -