Submission #738456

#	Time	Username	Problem	Language	Result	Execution time	Memory
738456		finn__	Zamjene (COCI16_zamjene)	C++17	84 / 140	4536 ms	418916 KiB

zamjene

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 1000001;
constexpr __int128_t B = 1000000007, Mod = (1LL << 61) - 1;

__int128_t p[N];
int32_t a[N], dsu[N];
map<uint32_t, uint64_t> def[N], over[N];
__int128_t defh[N], overh[N];
map<int64_t, unordered_map<int64_t, uint64_t>> mp;
size_t good_count, pair_count;

int32_t repr(int32_t u) { return dsu[u] < 0 ? u : dsu[u] = repr(dsu[u]); }

void dsu_merge(int32_t u, int32_t v)
{
    u = repr(u);
    v = repr(v);
    dsu[u] += dsu[v];
    dsu[v] = u;
}

bool dsu_same_set(int32_t u, int32_t v) { return repr(u) == repr(v); }

int32_t dsu_set_size(int32_t u) { return -dsu[repr(u)]; }

void erase_cloud(size_t i)
{
    if (!defh[i])
    {
        good_count--;
        return;
    }
    auto it = mp.find(overh[i]);
    if (it != mp.end())
    {
        auto jt = it->second.find(defh[i]);
        if (jt != it->second.end())
            pair_count -= dsu_set_size(i) * jt->second;
    }
    mp[defh[i]][overh[i]] -= dsu_set_size(i);
}

void insert_cloud(size_t i)
{
    if (!defh[i])
    {
        good_count++;
        return;
    }
    auto it = mp.find(overh[i]);
    if (it != mp.end())
    {
        auto jt = it->second.find(defh[i]);
        if (jt != it->second.end())
            pair_count += dsu_set_size(i) * jt->second;
    }
    mp[defh[i]][overh[i]] += dsu_set_size(i);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    p[0] = 1;
    for (size_t i = 1; i < N; ++i)
        p[i] = (p[i - 1] * B) % Mod;

    size_t n, q;
    cin >> n >> q;
    for (size_t i = 0; i < n; ++i)
        cin >> a[i], dsu[i] = a[i];
    sort(dsu, dsu + n);

    size_t num_components = n;
    for (size_t i = 0; i < n; ++i)
    {
        if (a[i] == dsu[i])
            good_count++;
        else
        {
            def[i][dsu[i]] = 1;
            over[i][a[i]] = 1;
            defh[i] = p[dsu[i]];
            overh[i] = p[a[i]];
            auto it = mp.find(overh[i]);
            if (it != mp.end())
            {
                auto jt = it->second.find(defh[i]);
                if (jt != it->second.end())
                    pair_count += jt->second;
            }
            mp[defh[i]][overh[i]]++;
        }
    }

    memset(dsu, 255, sizeof dsu);

    while (q--)
    {
        uint32_t t;
        cin >> t;

        if (t == 1)
        {
            uint32_t i, j;
            cin >> i >> j;
            --i, --j;
            if (repr(i) == repr(j))
                continue;
            erase_cloud(repr(i));
            erase_cloud(repr(j));
            for (auto const &k : {i, j})
            {
                auto const l = repr(k);
                auto it = over[l].find(a[k]);
                if (it != over[l].end() && it->second)
                {
                    overh[l] = (overh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
                    it->second--;
                    overh[l] = (overh[l] + p[a[k]] * it->second) % Mod;
                }
                else
                {
                    it = def[l].find(a[k]);
                    if (it != def[l].end())
                        defh[l] = (defh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
                    def[l][a[k]]++;
                    defh[l] = (defh[l] + p[a[k]] * def[l][a[k]]) % Mod;
                }
            }
            swap(a[i], a[j]);
            for (auto const &k : {i, j})
            {
                auto const l = repr(k);
                auto it = def[l].find(a[k]);
                if (it != def[l].end() && it->second)
                {
                    defh[l] = (defh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
                    it->second--;
                    defh[l] = (defh[l] + p[a[k]] * it->second) % Mod;
                }
                else
                {
                    it = over[l].find(a[k]);
                    if (it != over[l].end())
                        overh[l] = (overh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
                    over[l][a[k]]++;
                    overh[l] = (overh[l] + p[a[k]] * over[l][a[k]]) % Mod;
                }
            }
            insert_cloud(repr(i));
            insert_cloud(repr(j));
        }
        else if (t == 2)
        {
            uint32_t i, j;
            cin >> i >> j;
            --i, --j;
            if (dsu_same_set(i, j))
                continue;

            --num_components;
            if (dsu_set_size(i) < dsu_set_size(j))
                swap(i, j);
            i = repr(i);
            j = repr(j);
            erase_cloud(i);
            erase_cloud(j);

            for (auto &[elem, cnt] : over[j])
            {
                auto it = def[i].find(elem);
                if (it != def[i].end())
                {
                    defh[i] = (defh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
                    uint32_t x = min(it->second, cnt);
                    it->second -= x;
                    cnt -= x;
                    defh[i] = (defh[i] + p[elem] * it->second) % Mod;
                }
            }
            for (auto &[elem, cnt] : def[j])
            {
                auto it = over[i].find(elem);
                if (it != over[i].end())
                {
                    overh[i] = (overh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
                    uint32_t x = min(it->second, cnt);
                    it->second -= x;
                    cnt -= x;
                    overh[i] = (overh[i] + p[elem] * it->second) % Mod;
                }
            }
            for (auto &[elem, cnt] : over[j])
            {
                auto it = over[i].find(elem);
                if (it != over[i].end())
                    overh[i] = (overh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
                over[i][elem] += cnt;
                overh[i] = (overh[i] + p[elem] * over[i][elem]) % Mod;
            }
            for (auto &[elem, cnt] : def[j])
            {
                auto it = def[i].find(elem);
                if (it != def[i].end())
                    defh[i] = (defh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
                def[i][elem] += cnt;
                defh[i] = (defh[i] + p[elem] * def[i][elem]) % Mod;
            }

            dsu_merge(i, j);
            insert_cloud(i);
        }
        else if (t == 3)
        {
            cout << (good_count == num_components ? "DA" : "NE") << '\n';
        }
        else
        {
            cout << pair_count << '\n';
        }
    }
}

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