제출 #1301276

#제출 시각아이디문제언어결과실행 시간메모리
1301276vache_kocharyan장애물 (IOI25_obstacles)C++20
컴파일 에러
0 ms0 KiB
#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); }

컴파일 시 표준 에러 (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 |     }
      |     ^