Submission #281852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281852	2020-08-23T14:46:33 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 SQ = 10000;

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

ll seg[SQ][8*SQ];

ll 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;
map<pair<int,int>, int> go;
vector<pair<int,ll>> b[SQ];

void changeblock(int block){
	sort(a[block].begin(), a[block].end());
	for (int i = 0; i < 8*SQ; 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){
	go.clear();
	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 ++;
		go[it.first] = idx/SQ;
		a[idx/SQ].push_back(it);
	}
	for (int i = 0; i < numBlock; i++)
		changeblock(i);
}

void update(int P, int Q, ll K){
	if (mp.count({P,Q})){
		mp[{P,Q}] = K;
		int block = go[{P,Q}];
		for (int i = 0; i < a[block].size(); i++)
			if (a[block][i].first == make_pair(P,Q))
				a[block][i].second = K;
		changeblock(block);
		return;
	}
	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;
	go[{P,Q}] = block;
	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){
	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(V+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

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:56: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]
   56 |  for (int i = 0; i < b[block].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
game.cpp: In function 'void update(int, int, ll)':
game.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < a[block].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x19): relocation truncated to fit: R_X86_64_32S against symbol `std::ios_base::Init::_S_refcount' defined in .bss._ZNSt8ios_base4Init11_S_refcountE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x6b): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x80): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x8b): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xa0): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xab): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xba): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xcd): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xd4): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status