Submission #735476

#	Time	Username	Problem	Language	Result	Execution time	Memory
735476		GrindMachine	Zamjene (COCI16_zamjene)	C++17	70 / 140	6056 ms	91060 KiB

zamjene

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://bigprimes.org/ (for generating big prime MOD)


sol idea:
dsu + multiset hashing

*/

const ll MOD = 964863244005699737;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

struct DSU {
    vector<int> par, rankk, siz;
    vector<ll> hsh;
    map<ll, ll> hashes;
    ll cnt = 0;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        hsh = vector<ll>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];

        // cnt -= siz[u] * hashes[MOD - hsh[u]];
        // hashes[hsh[u]] -= siz[u];

        // cnt -= siz[v] * hashes[MOD - hsh[v]];
        // hashes[hsh[v]] -= siz[v];

        // hsh[u] = (hsh[u] + hsh[v]) % MOD;
        // siz[u] += siz[v];

        // cnt += siz[u] * hashes[MOD - hsh[u]];
        // hashes[hsh[u]] += siz[u];
    }
};

void solve(int test_case)
{
    ll n, q; cin >> n >> q;
    vector<ll> a(n + 5);
    rep1(i, n) cin >> a[i];

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<ll> dist(1, MOD - 1);

    auto b = a;
    sort(b.begin() + 1, b.begin() + n + 1);

    map<ll, ll> mp;
    rep1(i, n) {
        if (mp.count(a[i])) conts;
        mp[a[i]] = dist(rng);
    }

    DSU dsu(n + 5);

    rep1(i, n) {
        ll v = (mp[a[i]] - mp[b[i]] + MOD) % MOD;
        dsu.hsh[i] = v;
        dsu.cnt += dsu.hashes[MOD - v];
        dsu.hashes[v]++;
    }

    while (q--) {
        ll t; cin >> t;
        if (t == 1) {
            ll u, v; cin >> u >> v;
            swap(a[u], a[v]);

            // dsu.hashes.clear();
            // dsu.cnt = 0;

            // vector<ll> here[n + 5];
            // rep1(i, n) {
            //     ll p = dsu.find(i);
            //     here[p].pb(i);
            // }

            // rep1(p, n) {
            //     if (here[p].empty()) conts;

            //     dsu.hsh[p] = 0;
            //     trav(i, here[p]) {
            //         dsu.hsh[p] += mp[a[i]] - mp[b[i]];
            //         dsu.hsh[p] = (dsu.hsh[p] % MOD + MOD) % MOD;
            //     }

            //     ll siz = sz(here[p]);
            //     dsu.cnt += siz * dsu.hashes[MOD - dsu.hsh[p]];
            //     dsu.hashes[dsu.hsh[p]] += siz;
            // }





            // ll pu = dsu.find(u), pv = dsu.find(v);



            // dsu.cnt -= dsu.siz[pu] * dsu.hashes[MOD - dsu.hsh[pu]];
            // dsu.hashes[dsu.hsh[pu]] -= dsu.siz[pu];

            // dsu.hsh[pu] += mp[a[v]] - mp[a[u]];
            // dsu.hsh[pu] = (dsu.hsh[pu] % MOD + MOD) % MOD;

            // dsu.cnt += dsu.siz[pu] * dsu.hashes[MOD - dsu.hsh[pu]];
            // dsu.hashes[dsu.hsh[pu]] += dsu.siz[pu];



            // dsu.cnt -= dsu.siz[pv] * dsu.hashes[MOD - dsu.hsh[pv]];
            // dsu.hashes[dsu.hsh[pv]] -= dsu.siz[pv];

            // dsu.hsh[pv] += mp[a[u]] - mp[a[v]];
            // dsu.hsh[pv] = (dsu.hsh[pv] % MOD + MOD) % MOD;

            // dsu.cnt += dsu.siz[pv] * dsu.hashes[MOD - dsu.hsh[pv]];
            // dsu.hashes[dsu.hsh[pv]] += dsu.siz[pv];


            // swap(a[u], a[v]);
        }
        else if (t == 2) {
            ll u, v; cin >> u >> v;
            dsu.merge(u, v);

            // dsu.hashes.clear();
            // dsu.cnt = 0;

            // vector<ll> here[n + 5];
            // rep1(i, n) {
            //     ll p = dsu.find(i);
            //     here[p].pb(i);
            // }

            // rep1(p, n) {
            //     if (here[p].empty()) conts;

            //     dsu.hsh[p] = 0;
            //     trav(i, here[p]) {
            //         dsu.hsh[p] += mp[a[i]] - mp[b[i]];
            //         dsu.hsh[p] = (dsu.hsh[p] % MOD + MOD) % MOD;
            //     }

            //     ll siz = sz(here[p]);
            //     dsu.cnt += siz * dsu.hashes[MOD - dsu.hsh[p]];
            //     dsu.hashes[dsu.hsh[p]] += siz;
            // }
        }
        else if (t == 3) {
            bool ans = true;

            vector<ll> here[n + 5];
            rep1(i, n) {
                ll p = dsu.find(i);
                here[p].pb(i);
            }

            rep1(p, n) {
                if (here[p].empty()) conts;

                vector<ll> v1, v2;
                trav(i, here[p]) {
                    v1.pb(a[i]);
                    v2.pb(b[i]);
                }

                sort(all(v1)), sort(all(v2));
                if (v1 != v2) {
                    ans = false;
                }
            }

            if (ans) cout << "DA" << endl;
            else cout << "NE" << endl;

            // if (dsu.hashes[0] == n) cout << "DA" << endl;
            // else cout << "NE" << endl;
        }
        else {
            vector<ll> here[n + 5];
            rep1(i, n) {
                ll p = dsu.find(i);
                here[p].pb(i);
            }

            map<map<ll, ll>, ll> ma;
            ll ans = 0;

            rep1(p, n) {
                ll siz = sz(here[p]);
                if (!siz) conts;

                map<ll, ll> curr;
                trav(i, here[p]) {
                    curr[a[i]]++;
                    curr[b[i]]--;
                }

                vector<ll> toerase;
                trav(p, curr) {
                    if (!p.ss) {
                        toerase.pb(p.ff);
                    }
                }

                trav(x, toerase) {
                    curr.erase(x);
                }

                if (curr.empty()) conts;

                auto opp = curr;
                trav(p, opp) p.ss *= -1;

                ans += siz * ma[opp];
                ma[curr] += siz;
            }

            cout << ans << endl;

            // map<ll, ll> ma;
            // ll ans = 0;

            // rep1(p, n) {
            //     if (here[p].empty()) conts;

            //     ll hsh = 0;
            //     trav(i, here[p]) {
            //         hsh += mp[a[i]] - mp[b[i]];
            //         hsh = (hsh % MOD + MOD) % MOD;
            //     }

            //     ans += dsu.siz[p] * ma[MOD - hsh];
            //     ma[hsh] += dsu.siz[p];
            // }

            // cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14