Submission #1301276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301276		vache_kocharyan	Obstacles for a Llama (IOI25_obstacles)	C++20	Compilation error	0 ms	0 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

const int N = 4e5 + 10;
const int M = 2e5 + 10;
const int LOG = 21;

vector<int>T, H;
int n, m;

int log2_(int x)
{
	return 31 - __builtin_clz(x);
}
struct sparse_table
{
	vector<int>a;
	int sp_mx[M][LOG];
	int sp_mn[M][LOG];
	int id_mn[M][LOG];
	int id_mx[M][LOG];

	void build_sparse(vector<int>H)
	{
		int m_ = H.size();
		a = H;
		for (int i = 0; i < m_; i++)
		{
			sp_mn[i][0] = H[i];
			sp_mx[i][0] = H[i];
			id_mn[i][0] = i;
			id_mx[i][0] = i;
		}

		for (int j = 1; j < LOG; j++)
		{
			for (int i = 0; i + (1 << j) <= m_; i++)
			{
				int mid = i + (1 << (j - 1));

				if (sp_mx[i][j - 1] >= sp_mx[mid][j - 1]) {
					sp_mx[i][j] = sp_mx[i][j - 1];
					id_mx[i][j] = id_mx[i][j - 1];
				}
				else {
					sp_mx[i][j] = sp_mx[mid][j - 1];
					id_mx[i][j] = id_mx[mid][j - 1];
				}

				if (sp_mn[i][j - 1] <= sp_mn[mid][j - 1]) {
					sp_mn[i][j] = sp_mn[i][j - 1];
					id_mn[i][j] = id_mn[i][j - 1];
				}
				else {
					sp_mn[i][j] = sp_mn[mid][j - 1];
					id_mn[i][j] = id_mn[mid][j - 1];
				}
			}
		}
	}

	int query_mx(int l, int r)
	{
		int lg = log2_(r - l + 1);
		return max(sp_mx[l][lg], sp_mx[r - (1 << lg) + 1][lg]);
	}

	int query_mn(int l, int r)
	{
		int lg = log2_(r - l + 1);
		return min(sp_mn[l][lg], sp_mn[r - (1 << lg) + 1][lg]);
	}

	int query_id_mx(int l, int r)
	{
		int lg = log2_(r - l + 1);
		int a = sp_mx[l][lg], b = sp_mx[r - (1 << lg) + 1][lg];
		if (a >= b) return id_mx[l][lg];
		return id_mx[r - (1 << lg) + 1][lg];
	}

	int query_id_mn(int l, int r)
	{
		int lg = log2_(r - l + 1);
		int a = sp_mn[l][lg], b = sp_mn[r - (1 << lg) + 1][lg];
		if (a <= b) return id_mn[l][lg];
		return id_mn[r - (1 << lg) + 1][lg];
	}

}c_sp, r_sp;

bool is_free(int i, int j)
{
	return T[i] > H[j];
}

int l[N], r[N], right_most_x[N], left_most_x[N], t[N], mn_ind[N];

pair<int, int>find_lr(int ind, int S)
{
	int ansl = S, ansr = S;

	int L = 0, R = S;
	while (L <= R && L >= 0 && R < m)
	{
		int mid = (L + R) / 2;

		if (r_sp.query_mx(mid, S) < T[ind])
		{
			ansl = mid;
			R = mid - 1;
		}
		else
		{
			L = mid + 1;
		}
	}
	L = S, R = m - 1;
	while (L <= R && L >= 0 && R < m)
	{
		int mid = (L + R) / 2;

		if (r_sp.query_mx(S, mid) < T[ind])
		{
			ansr = mid;
			L = mid + 1;
		}
		else
		{
			R = mid - 1;
		}
	}
	return { ansl, ansr };
}

int nxt[N];

struct node
{
	int ind, t;
	bool operator<(node const& o) const {
		if (ind != o.ind) return ind < o.ind;
		return t < o.t;
	}
};

unordered_map<pair<int, int>, int>mp;

struct dsu_
{
	int p[N], sz[N];
	int n;
	void init(int _n)
	{
		n = _n;
		for (int i = 1; i <= n; i++)
			p[i] = i, sz[i] = 1;
	}

	int find(int a)
	{
		if (a != p[a])
			return p[a] = find(p[a]);
		return p[a];
	}

	void merge(int a, int b)
	{
		a = find(a), b = find(b);
		if (a == b)return;
		if (sz[a] < sz[b])swap(a, b);
		sz[a] += sz[b];
		sz[b] = 0;
		p[b] = a;
	}

	bool ask(int a, int b)
	{
		a = find(a);
		b = find(b);
		return (a == b);
	}
}dsu;

void initialize(std::vector<int> T, std::vector<int> H)
{
	n = T.size();
	m = H.size();
	::T = T;
	::H = H;

	r_sp.build_sparse(H);
	c_sp.build_sparse(T);

	int cnt = 0;
	queue<int>cur;

	for (int i = 0; i < m;)
	{
		if (is_free(0, i))
		{
			cnt++;
			cur.push(cnt);
			pair<int, int>P = find_lr(0, i);
			l[cnt] = P.first;
			r[cnt] = P.second;
			i = r[cnt] + 2;
			t[cnt] = 0;
			mp[{0, r_sp.query_id_mn(l[cnt], r[cnt])}] = cnt;
		}
		else i++;
	}

	while (!cur.empty()) {
		int i = cur.front();
		cur.pop();
		int ind = r_sp.query_id_mn(l[i], r[i]);
		int cur_mn = T[t[i]];
		int x = t[i] + 1;
		while (x < n)
		{
			cur_mn = min(cur_mn, T[x]);
			if (cur_mn <= H[ind])
				break;
			pair<int, int>P = find_lr(x, ind);
			if (P.first <= l[i] && P.second >= r[i])
			{
				if (P.first < l[i] || P.second > r[i]) 
				{
					pair<int, int> key = { x, r_sp.query_id_mn(P.first, P.second) };
					if (mp.count(key)) {
						nxt[i] = mp[key];
					}
					else {
						cnt++;
						l[cnt] = P.first;
						r[cnt] = P.second;
						t[cnt] = x;
						mp[key] = cnt;
						cur.push(cnt);
						nxt[i] = cnt;
					}
					break;
				}
			}
			x++;
		}
	}

	dsu.init(cnt + 10);

	for (int i = 1; i < cnt; i++)
		if (nxt[i])
			dsu.merge(i, nxt[i]);
}

bool can_reach(int L, int R, int S, int D)
{
	if (S > D) swap(S, D);

	pair<int, int>p1 = find_lr(0, S);
	pair<int, int>p2 = find_lr(0, D);

	int cnt1 = mp[{0, r_sp.query_id_mn(p1.first, p1.second)}];
	int cnt2 = mp[{0, r_sp.query_id_mn(p2.first, p2.second)}];

	return dsu.ask(cnt1, cnt2);
}

Compilation message (stderr)

obstacles.cpp:150:35: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]'
  150 | unordered_map<pair<int, int>, int>mp;
      |                                   ^~
In file included from /usr/include/c++/13/unordered_map:41,
                 from /usr/include/c++/13/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from obstacles.cpp:2:
/usr/include/c++/13/bits/unordered_map.h:148:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]' is implicitly deleted because the default definition would be ill-formed:
  148 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/13/bits/unordered_map.h:148:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/13/bits/unordered_map.h:33:
/usr/include/c++/13/bits/hashtable.h:530:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
  530 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/13/bits/hashtable.h:530:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/13/bits/hashtable.h:35:
/usr/include/c++/13/bits/hashtable_policy.h:1701:7: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
 1701 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1701:7: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]'
/usr/include/c++/13/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<int, int> >]':
/usr/include/c++/13/bits/hashtable_policy.h:1301:7:   required from here
/usr/include/c++/13/bits/hashtable_policy.h:1218:49: error: use of deleted function 'std::hash<std::pair<int, int> >::hash()'
 1218 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
In file included from /usr/include/c++/13/bits/stl_bvector.h:65,
                 from /usr/include/c++/13/vector:67,
                 from obstacles.h:1,
                 from obstacles.cpp:1:
/usr/include/c++/13/bits/functional_hash.h:102:12: note: 'std::hash<std::pair<int, int> >::hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/13/bits/functional_hash.h:102:12: error: no matching function for call to 'std::__hash_enum<std::pair<int, int>, false>::__hash_enum()'
/usr/include/c++/13/bits/functional_hash.h:83:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = std::pair<int, int>; bool <anonymous> = false]'
   83 |       __hash_enum(__hash_enum&&);
      |       ^~~~~~~~~~~
/usr/include/c++/13/bits/functional_hash.h:83:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/13/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/13/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/13/bits/hashtable_policy.h:1301:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]' is implicitly deleted because the default definition would be ill-formed:
 1301 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1301:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()'
/usr/include/c++/13/bits/hashtable_policy.h:1215:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed:
 1215 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1215:12: error: use of deleted function 'std::hash<std::pair<int, int> >::~hash()'
/usr/include/c++/13/bits/functional_hash.h:102:12: note: 'std::hash<std::pair<int, int> >::~hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/13/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context
/usr/include/c++/13/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/13/bits/hashtable_policy.h:1701:7: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
 1701 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1279:12: note: 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()' is implicitly deleted because the default definition would be ill-formed:
 1279 |     struct _Hash_code_base
      |            ^~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1279:12: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()'
/usr/include/c++/13/bits/hashtable.h:530:7: error: use of deleted function 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()'
  530 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1658:12: note: 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()' is implicitly deleted because the default definition would be ill-formed:
 1658 |     struct _Hashtable_base
      |            ^~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1658:12: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
/usr/include/c++/13/bits/hashtable.h:530:7: error: use of deleted function 'constexpr std::_Enable_default_constructor<false, _Tag>::_Enable_default_constructor() [with _Tag = std::__detail::_Hash_node_base]'
  530 |       _Hashtable() = default;
      |       ^~~~~~~~~~
In file included from /usr/include/c++/13/bits/hashtable.h:36:
/usr/include/c++/13/bits/enable_special_members.h:113:15: note: declared here
  113 |     constexpr _Enable_default_constructor() noexcept = delete;
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/13/bits/hashtable_policy.h:840:45:   required from 'std::__detail::_Map_base<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::mapped_type& std::__detail::_Map_base<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::operator[](key_type&&) [with _Key = std::pair<int, int>; _Val = int; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; mapped_type = int; key_type = std::pair<int, int>]'
/usr/include/c++/13/bits/unordered_map.h:991:20:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; mapped_type = int; key_type = std::pair<int, int>]'
obstacles.cpp:212:44:   required from here
/usr/include/c++/13/bits/hashtable_policy.h:1308:23: error: static assertion failed: hash function must be invocable with an argument of key type
 1308 |         static_assert(__is_invocable<const _Hash&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/hashtable_policy.h:1308:23: note: 'std::__is_invocable<const std::hash<std::pair<int, int> >&, const std::pair<int, int>&>()' evaluates to false
/usr/include/c++/13/bits/hashtable_policy.h:1310:25: error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::pair<int, int>&)'
 1310 |         return _M_hash()(__k);
      |                ~~~~~~~~~^~~~~
/usr/include/c++/13/bits/hashtable.h: In instantiation of 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::~_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]':
/usr/include/c++/13/bits/unordered_map.h:109:11:   required from here
/usr/include/c++/13/bits/hashtable.h:1610:5: error: use of deleted function 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()'
 1610 |     }
      |     ^