Submission #281813

#	Time	Username	Problem	Language	Result	Execution time	Memory
281813		Saboon	Game (IOI13_game)	C++14	0 / 100	1 ms	384 KiB

game

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

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

int seg[SQ][8*SQ];

int get(int id, int L, int R, int l, int r, int block){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r)
		return seg[block][id];
	int mid = (L + R) >> 1;
	return gcd2(get(2*id+0, L, mid, l, r, block),
				get(2*id+1, mid, R, l, r, block));
}

void change(int id, int L, int R, int idx, ll K, int block){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		seg[block][id] = K;
		return;
	}
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, idx, K, block);
	change(2*id+1, mid, R, idx, K, block);
	seg[block][id] = gcd2(seg[block][2*id+0], seg[block][2*id+1]);
}

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

void changeblock(int block){
	for (int i = 0; i < 4*305; i++)
		seg[block][i] = 0;
	b[block].clear();
	for (auto it : a[block])
		b[block].push_back({it.first.second,it.second});
	sort(b[block].begin(), b[block].end());
	for (int i = 0; i < b[block].size(); i++)
		change(1, 0, b[block].size(), i, b[block][i].second, block);
}

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);
	int idx = -1;
	for (auto it : mp){
		idx ++;
		a[idx/SQ].push_back(it);
	}
	for (int i = 0; i < numBlock; i++)
		changeblock(i);
}

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
		changeblock(block);
}

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].empty())
			continue;
		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){
			int lo = lower_bound(b[i].begin(), b[i].end(), make_pair(Q,-1LL)) - b[i].begin();
			int hi = lower_bound(b[i].begin(), b[i].end(), make_pair(U+1, -1LL)) - b[i].begin();
			answer = gcd2(answer, get(1, 0, b[i].size(), lo, hi, i));
			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 (stderr)

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 function 'void changeblock(int)':
game.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int i = 0; i < b[block].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
game.cpp:49:17: warning: iteration 1200 invokes undefined behavior [-Waggressive-loop-optimizations]
   49 |   seg[block][i] = 0;
      |   ~~~~~~~~~~~~~~^~~
game.cpp:48:20: note: within this loop
   48 |  for (int i = 0; i < 4*305; i++)
      |                  ~~^~~~~~~

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