제출 #739674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739674		scanhex	Game (IOI13_game)	C++17	컴파일 에러	0 ms	0 KiB

game

#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

#include "grader.h"

//pizda 

template<typename T> 
class fake_ptr {
	static vector<T> mem;
public:
	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();
	}
private:
	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 (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);
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp:6:10: fatal error: grader.h: No such file or directory
    6 | #include "grader.h"
      |          ^~~~~~~~~~
compilation terminated.