Submission #765317

#TimeUsernameProblemLanguageResultExecution timeMemory
765317PanosPaskZamjene (COCI16_zamjene)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define POSITIVE_M(v) (v = ((v%MOD) + MOD) % MOD) using namespace std; // typedef long long ll; typedef __int128_t ll; typedef __int128_t lll; const ll MOD = (1ll << 61) - 1; const int PRIME = 3; int n, Q; vector<int> a; vector<ll> pos_v; vector<ll> num_v; // DSU variables vector<ll> total_pos, total_num; vector<int> rep; vector<int> sz; unordered_map<ll, int> diff_looking; ll q4ans = 0; int find(int a) { if (rep[a] != a) rep[a] = find(rep[a]); return rep[a]; } void remove_option(int a) { a = find(a); ll diff = total_num[a] - total_pos[a]; POSITIVE_M(diff); if (diff == 0) return; int v = diff_looking[diff]; if (v == sz[a]) diff_looking.erase(diff); else diff_looking[diff] -= sz[a]; ll rev = -diff; POSITIVE_M(rev); if (diff_looking.find(rev) != diff_looking.end()) { int b = diff_looking[rev]; q4ans -= (ll)b * sz[a]; } } void add_option(int a) { a = find(a); ll diff = total_num[a] - total_pos[a]; POSITIVE_M(diff); if (diff == 0) return; diff_looking[diff] += sz[a]; ll rev = -diff; POSITIVE_M(rev); if (diff_looking.find(rev) != diff_looking.end()) { int b = diff_looking[rev]; q4ans += (ll)sz[a] * b; } } void init(void) { rep.resize(n); sz.assign(n, 1); total_pos.resize(n); total_num.resize(n); for (int i = 0; i < n; i++) { rep[i] = i; total_pos[i] = pos_v[i]; total_num[i] = num_v[a[i]]; add_option(i); } } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[b] > sz[a]) swap(a, b); remove_option(a); remove_option(b); rep[b] = a; sz[a] += sz[b]; total_num[a] += total_num[b]; POSITIVE_M(total_num[a]); total_pos[a] += total_pos[b]; POSITIVE_M(total_pos[a]); add_option(a); } void change_to(int a, int p_v, int n_v) { a = find(a); remove_option(a); total_num[a] += num_v[n_v] - num_v[p_v]; POSITIVE_M(total_num[a]); add_option(a); } ll bigger_rand(void) { ll a = rand(); ll b = rand(); ll res = (a * RAND_MAX) + b; return res; } int main(void) { scanf("%d %d", &n, &Q); num_v.assign(1e6 + 1, -1); pos_v.resize(n); a.resize(n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } srand(42); vector<int> s_a = a; sort(s_a.begin(), s_a.end()); for (int i = 0; i < n; i++) { if (num_v[s_a[i]] == -1) { num_v[s_a[i]] = bigger_rand() % MOD; POSITIVE_M(num_v[s_a[i]]); } pos_v[i] = num_v[s_a[i]]; } init(); while (Q--) { int op; scanf("%d", &op); if (op == 1) { int p1, p2; scanf("%d %d", &p1, &p2); p1--; p2--; change_to(p1, a[p1], a[p2]); change_to(p2, a[p2], a[p1]); swap(a[p1], a[p2]); } else if (op == 2) { int p1, p2; scanf("%d %d", &p1, &p2); p1--; p2--; unite(p1, p2); } else if (op == 3) { if (diff_looking.size()) printf("NE\n"); else printf("DA\n"); } else { printf("%lld\n", (long long)q4ans); } } return 0; }

Compilation message (stderr)

zamjene.cpp:22:24: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = __int128; _Tp = int; _Hash = std::hash<__int128>; _Pred = std::equal_to<__int128>; _Alloc = std::allocator<std::pair<const __int128, int> >]'
   22 | unordered_map<ll, int> diff_looking;
      |                        ^~~~~~~~~~~~
In file included from /usr/include/c++/10/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/unordered_map.h:141:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = __int128; _Tp = int; _Hash = std::hash<__int128>; _Pred = std::equal_to<__int128>; _Alloc = std::allocator<std::pair<const __int128, int> >]' is implicitly deleted because the default definition would be ill-formed:
  141 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/10/bits/unordered_map.h:141:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable() [with _Key = __int128; _Value = std::pair<const __int128, int>; _Alloc = std::allocator<std::pair<const __int128, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128>; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; _Hash = 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++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable.h:451:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable() [with _Key = __int128; _Value = std::pair<const __int128, int>; _Alloc = std::allocator<std::pair<const __int128, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128>; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; _Hash = 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:
  451 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/10/bits/hashtable.h:451:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base() [with _Key = __int128; _Value = std::pair<const __int128, int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128>; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable_policy.h:1791:5: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base() [with _Key = __int128; _Value = std::pair<const __int128, int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128>; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
 1791 |     _Hashtable_base() = default;
      |     ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1791:5: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base() [with _Key = __int128; _Value = std::pair<const __int128, int>; _ExtractKey = std::__detail::_Select1st; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing]'
/usr/include/c++/10/bits/hashtable_policy.h:1368:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base() [with _Key = __int128; _Value = std::pair<const __int128, int>; _ExtractKey = std::__detail::_Select1st; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing]' is implicitly deleted because the default definition would be ill-formed:
 1368 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1368:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<__int128>]'
/usr/include/c++/10/bits/hashtable_policy.h:1112:7: note: 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<__int128>]' is implicitly deleted because the default definition would be ill-formed:
 1112 |       _Hashtable_ebo_helper() = default;
      |       ^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1112:7: error: use of deleted function 'std::hash<__int128>::hash()'
In file included from /usr/include/c++/10/bits/basic_string.h:6787,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<__int128>::hash()' is implicitly deleted because the default definition would be ill-formed:
  101 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/10/bits/functional_hash.h:101:12: error: no matching function for call to 'std::__hash_enum<__int128, false>::__hash_enum()'
/usr/include/c++/10/bits/functional_hash.h:82:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = __int128; bool <anonymous> = false]'
   82 |       __hash_enum(__hash_enum&&);
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/functional_hash.h:82:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/10/bits/functional_hash.h:101:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = __int128; bool <anonymous> = false]' is private within this context
  101 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/10/bits/functional_hash.h:83:7: note: declared private here
   83 |       ~__hash_enum();
      |       ^
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable_policy.h:1112:7: error: use of deleted function 'std::hash<__int128>::~hash()'
 1112 |       _Hashtable_ebo_helper() = default;
      |       ^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/basic_string.h:6787,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<__int128>::~hash()' is implicitly deleted because the default definition would be ill-formed:
  101 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/10/bits/functional_hash.h:101:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = __int128; bool <anonymous> = false]' is private within this context
/usr/include/c++/10/bits/functional_hash.h:83:7: note: declared private here
   83 |       ~__hash_enum();
      |       ^
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable_policy.h:1368:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128>, true>::~_Hashtable_ebo_helper()'
 1368 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1109:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128>, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed:
 1109 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1109:12: error: use of deleted function 'std::hash<__int128>::~hash()'
/usr/include/c++/10/bits/hashtable_policy.h:1791:5: error: use of deleted function 'std::__detail::_Hash_code_base<__int128, std::pair<const __int128, int>, std::__detail::_Select1st, std::hash<__int128>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
 1791 |     _Hashtable_base() = default;
      |     ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1341:12: note: 'std::__detail::_Hash_code_base<__int128, std::pair<const __int128, int>, std::__detail::_Select1st, std::hash<__int128>, 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:
 1341 |     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1342 |       _Default_ranged_hash, true>
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1341:12: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<__int128>, true>::~_Hashtable_ebo_helper()'
In file included from /usr/include/c++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable.h:451:7: error: use of deleted function 'std::__detail::_Hashtable_base<__int128, std::pair<const __int128, int>, std::__detail::_Select1st, std::equal_to<__int128>, std::hash<__int128>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()'
  451 |       _Hashtable() = default;
      |       ^~~~~~~~~~
In file included from /usr/include/c++/10/bits/hashtable.h:35,
                 from /usr/include/c++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable_policy.h:1725:10: note: 'std::__detail::_Hashtable_base<__int128, std::pair<const __int128, int>, std::__detail::_Select1st, std::equal_to<__int128>, std::hash<__int128>, 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:
 1725 |   struct _Hashtable_base
      |          ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1725:10: error: use of deleted function 'std::__detail::_Hash_code_base<__int128, std::pair<const __int128, int>, std::__detail::_Select1st, std::hash<__int128>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
/usr/include/c++/10/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = __int128; _Value = std::pair<const __int128, int>; _ExtractKey = std::__detail::_Select1st; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = long unsigned int]':
/usr/include/c++/10/bits/hashtable_policy.h:707:45:   required from 'std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::mapped_type& std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::operator[](const key_type&) [with _Key = __int128; _Pair = std::pair<const __int128, int>; _Alloc = std::allocator<std::pair<const __int128, int> >; _Equal = std::equal_to<__int128>; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::mapped_type = int; std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::key_type = __int128]'
/usr/include/c++/10/bits/unordered_map.h:984:20:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type&) [with _Key = __int128; _Tp = int; _Hash = std::hash<__int128>; _Pred = std::equal_to<__int128>; _Alloc = std::allocator<std::pair<const __int128, int> >; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type = int; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type = __int128]'
zamjene.cpp:45:30:   required from here
/usr/include/c++/10/bits/hashtable_policy.h:1377:16: error: static assertion failed: hash function must be invocable with an argument of key type
 1377 |  static_assert(__is_invocable<const _H1&, const _Key&>{},
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/hashtable_policy.h:1379:16: error: no match for call to '(const std::hash<__int128>) (const __int128&)'
 1379 |  return _M_h1()(__k);
      |         ~~~~~~~^~~~~
In file included from /usr/include/c++/10/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:117,
                 from zamjene.cpp:1:
/usr/include/c++/10/bits/hashtable.h: In instantiation of 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::~_Hashtable() [with _Key = __int128; _Value = std::pair<const __int128, int>; _Alloc = std::allocator<std::pair<const __int128, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<__int128>; _H1 = std::hash<__int128>; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]':
/usr/include/c++/10/bits/unordered_map.h:102:11:   required from here
/usr/include/c++/10/bits/hashtable.h:1389:5: error: use of deleted function 'std::__detail::_Hashtable_base<__int128, std::pair<const __int128, int>, std::__detail::_Select1st, std::equal_to<__int128>, std::hash<__int128>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::~_Hashtable_base()'
 1389 |     }
      |     ^
zamjene.cpp: In function 'int main()':
zamjene.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%d %d", &n, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
zamjene.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
zamjene.cpp:180:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |             scanf("%d %d", &p1, &p2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
zamjene.cpp:190:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |             scanf("%d %d", &p1, &p2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~