oj.uz

Submission #739688

# Submission time Handle Problem Language Result Execution time Memory
739688 2023-05-11T04:04:03 Z scanhex Game (IOI13_game) C++17
80 / 100
 9322 ms 256000 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1012 ms 11760 KB Output is correct
5 Correct 576 ms 11988 KB Output is correct
6 Correct 729 ms 8928 KB Output is correct
7 Correct 895 ms 8564 KB Output is correct
8 Correct 533 ms 6184 KB Output is correct
9 Correct 862 ms 8700 KB Output is correct
10 Correct 912 ms 8408 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2633 ms 21616 KB Output is correct
13 Correct 4056 ms 18076 KB Output is correct
14 Correct 978 ms 17804 KB Output is correct
15 Correct 4408 ms 20684 KB Output is correct
16 Correct 437 ms 20744 KB Output is correct
17 Correct 1630 ms 12960 KB Output is correct
18 Correct 3594 ms 21124 KB Output is correct
19 Correct 2823 ms 21348 KB Output is correct
20 Correct 2771 ms 20676 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 997 ms 11972 KB Output is correct
13 Correct 580 ms 12156 KB Output is correct
14 Correct 766 ms 8920 KB Output is correct
15 Correct 930 ms 8592 KB Output is correct
16 Correct 521 ms 6220 KB Output is correct
17 Correct 891 ms 8668 KB Output is correct
18 Correct 864 ms 8288 KB Output is correct
19 Correct 2435 ms 21560 KB Output is correct
20 Correct 4003 ms 17992 KB Output is correct
21 Correct 1002 ms 17644 KB Output is correct
22 Correct 4300 ms 20712 KB Output is correct
23 Correct 448 ms 20816 KB Output is correct
24 Correct 1602 ms 13088 KB Output is correct
25 Correct 3644 ms 21108 KB Output is correct
26 Correct 2794 ms 21224 KB Output is correct
27 Correct 2726 ms 20584 KB Output is correct
28 Correct 2079 ms 251932 KB Output is correct
29 Correct 4032 ms 256000 KB Output is correct
30 Correct 8630 ms 162628 KB Output is correct
31 Correct 7818 ms 136488 KB Output is correct
32 Correct 1945 ms 50456 KB Output is correct
33 Correct 2470 ms 52568 KB Output is correct
34 Correct 869 ms 255484 KB Output is correct
35 Correct 2479 ms 140068 KB Output is correct
36 Correct 5469 ms 256000 KB Output is correct
37 Correct 4235 ms 256000 KB Output is correct
38 Correct 4290 ms 256000 KB Output is correct
39 Correct 3524 ms 204272 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1014 ms 11864 KB Output is correct
13 Correct 601 ms 12020 KB Output is correct
14 Correct 765 ms 8752 KB Output is correct
15 Correct 985 ms 8576 KB Output is correct
16 Correct 535 ms 6180 KB Output is correct
17 Correct 887 ms 8580 KB Output is correct
18 Correct 892 ms 8256 KB Output is correct
19 Correct 2419 ms 21504 KB Output is correct
20 Correct 4218 ms 18180 KB Output is correct
21 Correct 971 ms 17640 KB Output is correct
22 Correct 4413 ms 20584 KB Output is correct
23 Correct 481 ms 20780 KB Output is correct
24 Correct 1648 ms 12900 KB Output is correct
25 Correct 3638 ms 21064 KB Output is correct
26 Correct 2839 ms 21448 KB Output is correct
27 Correct 2823 ms 20604 KB Output is correct
28 Correct 2005 ms 252552 KB Output is correct
29 Correct 4019 ms 256000 KB Output is correct
30 Correct 9322 ms 162528 KB Output is correct
31 Correct 8388 ms 136440 KB Output is correct
32 Correct 1929 ms 50448 KB Output is correct
33 Correct 2501 ms 52560 KB Output is correct
34 Correct 933 ms 255456 KB Output is correct
35 Correct 2760 ms 140092 KB Output is correct
36 Correct 6040 ms 256000 KB Output is correct
37 Correct 4455 ms 256000 KB Output is correct
38 Correct 4909 ms 256000 KB Output is correct
39 Runtime error 1106 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -