Submission #739688

#	Time	Username	Problem	Language	Result	Execution time	Memory
739688		scanhex	Game (IOI13_game)	C++17	80 / 100	9322 ms	256000 KiB

game

#include <bits/stdc++.h>
 
using namespace std;
typedef long long nagai;
 
#include "game.h"
 
//pizda 
 
template<typename T> 
class fake_ptr {
public:
	static vector<T>& mem() {
		static vector<T> mem_;
		return mem_;
	}
	static void reserve(int cnt) {
		mem().reserve(cnt);
	}
	static fake_ptr make() {
		mem().push_back({});
		return fake_ptr{static_cast<uint32_t>(mem().size() - 1)};
	}
	fake_ptr(){}
	explicit fake_ptr(uint32_t arr_ind) : arr_ind{arr_ind} {};
	T* operator ->() {
		assert(arr_ind);
		return &mem()[*arr_ind];
	}
	fake_ptr& operator=(const fake_ptr& o) {
		arr_ind = o.arr_ind;
		return *this;
	}
	operator bool() {
		return arr_ind.has_value();
	}
	std::optional<std::uint32_t> arr_ind;
};
 
//template<typename T>
//vector<T> fake_ptr<T>::mem = {};
 
template<typename T>
fake_ptr<T> make_fake() {
	return fake_ptr<T>::make();
}
 
 
nagai gcd(nagai a, nagai b)
{
	while (b)
		a = a % b, swap(a, b);
	return a;
}
 
template<int H>
struct sl
{
	struct nd
	{
		vector<fake_ptr<nd>> ri;
		vector<nagai> gcd;
//		vector<int> len;
		pair<int, int> x;
		inline int sz()
		{
			return ri.size();
		}
	};
	fake_ptr<nd> header;
	sl() {
		header = make_fake<nd>();
		header->ri.resize(H, {});
		header->gcd.resize(H, 0);
		header->x = {-1, -1};
		//header->len.resize(H, 0);
	}
	fake_ptr<nd> last[H];
	int len[H];
	void go(pair<int, int> to)
	{
		fake_ptr<nd> cur = header;
		for (int i = H - 1; i >= 0; --i)
		{
			while (i < cur->ri.size() && cur->ri[i] && cur->ri[i]->x < to)
				cur = cur->ri[i];
			last[i] = cur;
		}
	}
	inline nagai calc(fake_ptr<nd> a, fake_ptr<nd> b, int i)
	{
		nagai g = a->gcd[i];
		while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
			a = a->ri[i], g = gcd(g, a->gcd[i]);
		//cerr << a->x << ' ' << (b ? b->x : -2) << ' ' << i << ' ' << g << endl;
		return g;
	}
	void insert(pair<int, int> ind, nagai val)
	{
		go(ind);
		fake_ptr<nd> nw = make_fake<nd>();
		nw->x = ind;
		for (int i = 0, add = 1; i < H; add &= rand(), ++i)
		{
			if (add)
			{
				if (i > 0)
				{
					nagai g = calc(last[i], nw, i - 1);
					nagai g1 = calc(nw, last[i]->ri[i], i - 1);
					//cerr << "kek " << g << ' ' << last[i]->x << ' ' << last[i]->gcd[i - 1] << endl;
					last[i]->gcd[i] = g;
					nw->gcd.push_back(g1);
				}
				else
					nw->gcd.push_back(val);
				nw->ri.push_back(last[i]->ri[i]);
				last[i]->ri[i] = nw;
			}
			else
			{
				last[i]->gcd[i] = gcd(last[i]->gcd[i], val);
			}
		}
	}
	void erase(pair<int, int> ind)
	{
		go(ind);
		for (int i = 0; i < H; ++i)
		{
			if (last[i]->ri[i] && last[i]->ri[i]->x == ind)
			{
				if (i)
					last[i]->gcd[i] = calc(last[i], last[i]->ri[i]->ri[i], i - 1);
				last[i]->ri[i] = last[i]->ri[i]->ri[i];
			}
			else
				last[i]->gcd[i] = calc(last[i], last[i]->ri[i], i - 1);
		}
	}
	void print()
	{
		for (int i = 0; i < H; ++i)
		{
			auto v = header;
			while (v)
				cerr << '{' << v->x.first << ',' << v->x.second << '}' << ',' << v->gcd[i] << ' ', v = v->ri[i];
			cerr << endl;
		}
	}
	nagai get(pair<int, int> l, pair<int, int> r)
	{
		nagai g = 0;
		go(l);
		fake_ptr<nd> kek = last[0]->ri[0];
		if (!kek)
			return 0;
		//cerr << kek->x.first << ' ' << kek->x.second << endl;
		for (int i = 0; i < H; ++i)
			while (i < kek->sz() && i + 1 >= kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
				g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
		//cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
		for (int i = H - 1; i >= 0; --i)
			while (i < kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
				g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
		//cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
		if (kek->x < r)
			g = gcd(g, kek->gcd[0]);
		return g;
	}
};
 
struct nd
{
	nd* le;
	nd* ri;
	sl<18> skip;
	nd() 
		: le(nullptr), ri(nullptr)
	{}
	void children()
	{
		if (!le)
			le = new nd();
		if (!ri)
			ri = new nd();
	}
	void add(int l, int r, int x, int y, nagai val, bool add)
	{
		if (l > x || r <= x)
			return;
		if (add)
			skip.insert({y, x}, val);
		else
			skip.erase({y, x});
		if (r - l == 1)
			return;
		children();
		int m = (l + r) / 2;
		le->add(l, m, x, y, val, add);
		ri->add(m, r, x, y, val, add);
	}
	nagai get(int l, int r, int ql1, int qr1, int ql2, int qr2)
	{
		//skip.print();
		if (l >= qr1 || ql1 >= r)
			return 0;
		if (ql1 <= l && r <= qr1)
			return skip.get({ql2, ql1}, {qr2, ql1});
		if (!le && !ri) 
			return 0;
		int m = (l + r) / 2;
		if (!le) 
			return ri->get(m, r, ql1, qr1, ql2, qr2);
		if (!ri) 
			return le->get(l, m, ql1, qr1, ql2, qr2);
		return gcd(le->get(l, m, ql1, qr1, ql2, qr2),
				ri->get(m, r, ql1, qr1, ql2, qr2));
	}
};
 
nd* rt = new nd;
 
int MX = 1000000000;
set<pair<int, int>> p;
 
void init(int R, int C)
{
	MX = R;
}
 
void update(int x, int y, long long t)
{
	if (p.count({x, y}))
		rt->add(0, MX, x, y, t, 0);
	rt->add(0, MX, x, y, t, 1);
	p.insert({x, y});
}
 
long long calculate(int xl, int yl, int xr, int yr)
{
    return rt->get(0, MX, xl, xr + 1, yl, yr + 1);
}

Compilation message (stderr)

game.cpp: In instantiation of 'void sl<H>::go(std::pair<int, int>) [with int H = 18]':
game.cpp:100:3:   required from 'void sl<H>::insert(std::pair<int, int>, nagai) [with int H = 18; nagai = long long int]'
game.cpp:193:27:   required from here
game.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fake_ptr<sl<18>::nd>, std::allocator<fake_ptr<sl<18>::nd> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    while (i < cur->ri.size() && cur->ri[i] && cur->ri[i]->x < to)
      |           ~~^~~~~~~~~~~~~~~~
game.cpp: In instantiation of 'nagai sl<H>::calc(fake_ptr<sl<H>::nd>, fake_ptr<sl<H>::nd>, int) [with int H = 18; nagai = long long int]':
game.cpp:109:16:   required from 'void sl<H>::insert(std::pair<int, int>, nagai) [with int H = 18; nagai = long long int]'
game.cpp:193:27:   required from here
game.cpp:93:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   93 |   while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
      |          ~~~^~~~~~~~~

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