제출 #1300746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300746		vache_kocharyan	Obstacles for a Llama (IOI25_obstacles)	C++20	컴파일 에러	0 ms	0 KiB

obstacles

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

using namespace std;

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

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

struct sparse_table
{
	vector<int>a;
	int sp_mx[N][LOG];
	int sp_mn[N][LOG];
	int id_mn[N][LOG];
	int id_mx[N][LOG];

	void build_sparse(vector<int>H)
	{
		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, ansr;
	
	int l = 0, r = S;
	while (l <= r)
	{
		int mid = (l + r) / 2l;

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

		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;
};

map<node, 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];
		return p[a] = find(p[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];
		p[b] = a;
	}

	bool ask(int a, int b)
	{
		a = find(a);
		b = find(b);
		if (a == b)return true;
		else return false;
	}
}dsu;

void initialize(std::vector<int> T, std::vector<int> H) 
{
	n = T.size();
	m = H.size();
	(::T).resize(n);
	(::H).resize(m);
	for (int i = 0; i < n; i++)(::T)[i] = T[i];
	for (int i = 0; i < m; i++)(::H)[i] = H[i];

	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();
		int ind = r_sp.query_id_mn(l[i], r[i]);

		int x = t[i];
		bool bol = true;
		while (x < n)
		{
			if (!bol)break;
			x++;
			if (c_sp.query_id_mn(t[i], x) <= H[ind])
				break;
			pair<int, int>P;
			P = find_lr(x, ind);
			if (P.first <= l[i] && P.second >= r[i])
			{
				if (mp[{x, r_sp.query_id_mn(P.first, P.second)}]) {
					break;
				}
				cnt++;
				l[cnt] = P.first;
				r[cnt] = P.second;
				t[cnt] = x;
				mp[{x, r_sp.query_id_mn(P.first, P.second)}] = cnt;
				cur.push(cnt);
				nxt[i] = cnt;
				break;
			}
		}
	}

	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);
	if (dsu.ask(S, D))return true;
	else return false;
}

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

In file included from /usr/include/c++/13/bits/refwrap.h:39,
                 from /usr/include/c++/13/vector:68,
                 from obstacles.h:1,
                 from obstacles.cpp:1:
/usr/include/c++/13/bits/stl_function.h: In instantiation of 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]':
/usr/include/c++/13/bits/stl_map.h:531:32:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](key_type&&) [with _Key = node; _Tp = int; _Compare = std::less<node>; _Alloc = std::allocator<std::pair<const node, int> >; mapped_type = int; key_type = node]'
obstacles.cpp:202:44:   required from here
/usr/include/c++/13/bits/stl_function.h:408:20: error: no match for 'operator<' (operand types are 'const node' and 'const node')
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/vector:62:
/usr/include/c++/13/bits/stl_iterator.h:583:5: note: candidate: 'template<class _IteratorL, class _IteratorR>  requires  three_way_comparable_with<_IteratorR, _IteratorL, std::partial_ordering> constexpr std::compare_three_way_result_t<_IteratorL, _IteratorR> std::operator<=>(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)' (reversed)
  583 |     operator<=>(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:583:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::reverse_iterator<_IteratorL>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1690:5: note: candidate: 'template<class _IteratorL, class _IteratorR>  requires  three_way_comparable_with<_IteratorR, _IteratorL, std::partial_ordering> constexpr std::compare_three_way_result_t<_IteratorL, _IteratorR> std::operator<=>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)' (reversed)
 1690 |     operator<=>(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1690:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::move_iterator<_IteratorL>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/bits/stl_pair.h:819:5: note: candidate: 'template<class _T1, class _T2> constexpr std::common_comparison_category_t<decltype (std::__detail::__synth3way(declval<_T1&>(), declval<_T1&>())), decltype (std::__detail::__synth3way(declval<_T2&>(), declval<_T2&>()))> std::operator<=>(const pair<_T1, _T2>&, const pair<_T1, _T2>&)' (rewritten)
  819 |     operator<=>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:819:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::pair<_T1, _T2>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:601:5: note: candidate: 'template<class _Iterator>  requires  three_way_comparable<_Iterator, std::partial_ordering> constexpr std::compare_three_way_result_t<_Iterator, _Iterator> std::operator<=>(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorL>&)' (rewritten)
  601 |     operator<=>(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:601:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::reverse_iterator<_IteratorL>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1756:5: note: candidate: 'template<class _Iterator>  requires  three_way_comparable<_Iterator, std::partial_ordering> constexpr std::compare_three_way_result_t<_Iterator, _Iterator> std::operator<=>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)' (rewritten)
 1756 |     operator<=>(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1756:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::move_iterator<_IteratorL>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:2059:5: note: candidate: 'template<class _Tp, class _Alloc> constexpr std::__detail::__synth3way_t<_T1> std::operator<=>(const vector<_Tp, _Alloc>&, const vector<_Tp, _Alloc>&)' (rewritten)
 2059 |     operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:2059:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::vector<_Tp, _Alloc>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:550:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&) requires requires{{std::operator<::__x->base() > std::operator<::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}'
  550 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:550:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::reverse_iterator<_IteratorL>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1705:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&) requires requires{{std::operator<::__x->base() < std::operator<::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}'
 1705 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1705:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:408:20: note:   'const node' is not derived from 'const std::move_iterator<_IteratorL>'
  408 |       { return __x < __y; }
      |                ~~~~^~~~~