Submission #201651

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
201651	2020-02-11T16:00:46 Z	SamAnd	Zamjene (COCI16_zamjene)	C++17	Compilation error	0 ms	0 KB

zamjene

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 1000006;
const int P = 1000003;
const int M = 1000000007;
const int P1 = 2000003;
const int M1 = 1000000009;
int ast[N], ast1[N];
void pre()
{
    ast[0] = 1;
    ast1[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        ast[i] = (ast[i - 1] * 1LL * P) % M;
        ast1[i] = (ast1[i - 1] * 1LL * P1) % M1;
    }
}

int n, qqq;
int a[N], b[N];

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

void ave(pair<int, int> x, int q)
{
    mp[x] += q;
    if (mp[x] == 0)
        mp.erase(x);
    if (x.first || x.second)
    {
        ans4 += mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] * 1LL * q;
        if (mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] == 0)
            mp.erase(m_p((M - x.first) % M, (M1 - x.second) % M1));
    }
}

void han(pair<int, int> x, int q)
{
    mp[x] -= q;
    if (mp[x] == 0)
        mp.erase(x);
    if (x.first || x.second)
    {
        ans4 -= mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] * 1LL * q;
        if (mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] == 0)
            mp.erase(m_p((M - x.first) % M, (M1 - x.second) % M1));
    }
}

int p[N];
int ha[N], hb[N];
int ha1[N], hb1[N];
int qq[N];

int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

pair<int, int> u(int x)
{
    return m_p((ha[x] - hb[x] + M) % M, (ha1[x] - hb1[x] + M1) % M1);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    pre();
    scanf("%d%d", &n, &qqq);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        p[i] = i;
        ha[i] = ast[a[i]];
        hb[i] = ast[b[i]];
        ha1[i] = ast1[a[i]];
        hb1[i] = ast1[b[i]];
        qq[i] = 1;
        ave(u(i), qq[i]);
    }
    while (qqq--)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (fi(x) == fi(y))
                continue;
            int xx = fi(x);
            int yy = fi(y);
            han(u(xx), qq[xx]);
            han(u(yy), qq[yy]);
            ha[xx] = (ha[xx] - ast[a[x]] + M) % M;
            ha[yy] = (ha[yy] - ast[a[y]] + M) % M;
            ha1[xx] = (ha1[xx] - ast1[a[x]] + M1) % M1;
            ha1[yy] = (ha1[yy] - ast1[a[y]] + M1) % M1;
            swap(a[x], a[y]);
            ha[xx] = (ha[xx] + ast[a[x]]) % M;
            ha[yy] = (ha[yy] + ast[a[y]]) % M;
            ha1[xx] = (ha1[xx] + ast1[a[x]]) % M1;
            ha1[yy] = (ha1[yy] + ast1[a[y]]) % M1;
            ave(u(xx), qq[xx]);
            ave(u(yy), qq[yy]);
        }
        else if (ty == 2)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (fi(x) == fi(y))
                continue;
            x = fi(x);
            y = fi(y);
            han(u(x), qq[x]);
            han(u(y), qq[y]);
            p[x] = y;
            ha[y] = (ha[y] + ha[x]) % M;
            hb[y] = (hb[y] + hb[x]) % M;
            ha1[y] = (ha1[y] + ha1[x]) % M1;
            hb1[y] = (hb1[y] + hb1[x]) % M1;
            qq[y] += qq[x];
            ave(u(y), qq[y]);
        }
        else if (ty == 3)
        {
            if (mp[m_p(0, 0)] == n)
                printf("DA\n");
            else
                printf("NE\n");
        }
        else
        {
            printf("%lld\n", ans4);
        }
    }
    return 0;
}

Compilation message

In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/c++/7/functional:60,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from zamjene.cpp:1:
/usr/include/c++/7/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > >':
/usr/include/c++/7/type_traits:143:12:   required from 'struct std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > >'
/usr/include/c++/7/type_traits:154:31:   required from 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<int, int>, int>'
zamjene.cpp:24:36:   required from here
/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::pair<int, int>&)'
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from zamjene.cpp:1:
/usr/include/c++/7/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >':
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<int, int>, int>'
zamjene.cpp:24:36:   required from here
/usr/include/c++/7/type_traits:154:31: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > >'
     : public __bool_constant<!bool(_Pp::value)>
                               ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/unordered_map:48:0,
                 from /usr/include/c++/7/functional:60,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from zamjene.cpp:1:
/usr/include/c++/7/bits/unordered_map.h: In instantiation of 'class std::unordered_map<std::pair<int, int>, int>':
zamjene.cpp:24:36:   required from here
/usr/include/c++/7/bits/unordered_map.h:103:66: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
                                                                  ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:110:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::key_type key_type;
                                             ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:111:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::value_type value_type;
                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:112:48: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::mapped_type mapped_type;
                                                ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:113:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::hasher hasher;
                                           ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:114:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::key_equal key_equal;
                                              ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:115:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:120:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::pointer  pointer;
                                             ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:121:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:122:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::reference  reference;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:123:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:124:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::iterator  iterator;
                                              ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:125:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:126:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:127:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:128:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::size_type  size_type;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:129:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:133:55: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       using node_type = typename _Hashtable::node_type;
                                                       ^
/usr/include/c++/7/bits/unordered_map.h:134:73: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       using insert_return_type = typename _Hashtable::insert_return_type;
                                                                         ^
/usr/include/c++/7/bits/unordered_map.h:288:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       operator=(initializer_list<value_type> __l)
       ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:386:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
  emplace(_Args&&... __args)
  ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:469:9: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
         try_emplace(const key_type& __k, _Args&&... __args)
         ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:487:9: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
         try_emplace(key_type&& __k, _Args&&... __args)
         ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:578:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:584:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:591:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
  insert(_Pair&& __x)
  ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:657:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:685:9: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
         insert_or_assign(const key_type& __k, _Obj&& __obj)
         ^~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:703:9: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
         insert_or_assign(key_type&& __k, _Obj&& __obj)
         ^~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:953:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       equal_range(const key_type& __x)
       ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:957:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       equal_range(const key_type& __x) const
       ^~~~~~~~~~~
zamjene.cpp: In function 'void ave(std::pair<int, int>, int)':
zamjene.cpp:29:7: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
     mp[x] += q;
       ^
zamjene.cpp:30:11: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
     if (mp[x] == 0)
           ^
zamjene.cpp:31:12: error: 'class std::unordered_map<std::pair<int, int>, int>' has no member named 'erase'
         mp.erase(x);
            ^~~~~
zamjene.cpp:34:19: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
         ans4 += mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] * 1LL * q;
                   ^
zamjene.cpp:35:15: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
         if (mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] == 0)
               ^
zamjene.cpp:36:16: error: 'class std::unordered_map<std::pair<int, int>, int>' has no member named 'erase'
             mp.erase(m_p((M - x.first) % M, (M1 - x.second) % M1));
                ^~~~~
zamjene.cpp: In function 'void han(std::pair<int, int>, int)':
zamjene.cpp:42:7: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
     mp[x] -= q;
       ^
zamjene.cpp:43:11: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
     if (mp[x] == 0)
           ^
zamjene.cpp:44:12: error: 'class std::unordered_map<std::pair<int, int>, int>' has no member named 'erase'
         mp.erase(x);
            ^~~~~
zamjene.cpp:47:19: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
         ans4 -= mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] * 1LL * q;
                   ^
zamjene.cpp:48:15: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
         if (mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] == 0)
               ^
zamjene.cpp:49:16: error: 'class std::unordered_map<std::pair<int, int>, int>' has no member named 'erase'
             mp.erase(m_p((M - x.first) % M, (M1 - x.second) % M1));
                ^~~~~
zamjene.cpp: In function 'int main()':
zamjene.cpp:137:19: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and 'std::pair<int, int>')
             if (mp[m_p(0, 0)] == n)
                   ^
zamjene.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &qqq);
     ~~~~~^~~~~~~~~~~~~~~~~~
zamjene.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
zamjene.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
zamjene.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~