Submission #676346

#	Time	Username	Problem	Language	Result	Execution time	Memory
676346		finn__	Zamjene (COCI16_zamjene)	C++17	0 / 140	5143 ms	226444 KiB

zamjene

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

#define MOD 1000000009
#define BASE 10016

int main()
{
    size_t n, q;
    cin >> n >> q;

    vector<int64_t> y(n);
    for (int64_t &x : y)
        cin >> x;
    vector<int64_t> z(y.begin(), y.end());
    sort(z.begin(), z.end());
    vector<int64_t> p(1000001);
    p[0] = 1;
    for (size_t i = 1; i < p.size(); i++)
        p[i] = (p[i - 1] * BASE) % MOD;

    vector<size_t> comp(n);
    vector<set<size_t>> comp_set(n);
    for (size_t i = 0; i < n; i++)
    {
        comp[i] = i;
        comp_set[i] = {i};
    }

    vector<int64_t> h1(n), h2(n);
    for (size_t i = 0; i < n; i++)
    {
        h1[i] = p[y[i]];
        h2[i] = p[z[i]];
    }

    set<size_t> cant_sort;
    for (size_t i = 0; i < n; i++)
        if (h1[i] != h2[i])
            cant_sort.insert(i);

    map<int64_t, size_t> d;
    size_t num_pairs = 0;

    for (size_t i = 0; i < n; i++)
    {
        if (h1[i] != h2[i])
        {
            num_pairs += d[-(h1[i] - h2[i])];
            d[h1[i] - h2[i]]++;
        }
    }

    for (size_t i = 0; i < q; i++)
    {
        int t;
        cin >> t;

        switch (t)
        {
        case 1:
        {
            int64_t a, b;
            cin >> a >> b;
            a--, b--;

            if (comp[a] == comp[b])
                break;

            if (h1[comp[a]] != h2[comp[a]])
            {
                num_pairs -= comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
                d[h1[comp[a]] - h2[comp[a]]] -= comp_set[comp[a]].size();
            }
            if (h1[comp[b]] != h2[comp[b]])
            {
                num_pairs -= comp_set[comp[b]].size() * d[h2[comp[b]] - h1[comp[b]]];
                d[h1[comp[b]] - h2[comp[b]]] -= comp_set[comp[b]].size();
            }

            h1[comp[a]] = (h1[comp[a]] - p[y[a]] + p[y[b]] + MOD) % MOD;
            h1[comp[b]] = (h1[comp[b]] - p[y[b]] + p[y[a]] + MOD) % MOD;

            if (h1[comp[a]] != h2[comp[a]])
            {
                num_pairs += comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
                d[h1[comp[a]] - h2[comp[a]]] += comp_set[comp[a]].size();
            }
            if (h1[comp[b]] != h2[comp[b]])
            {
                num_pairs += comp_set[comp[b]].size() * d[h2[comp[b]] - h1[comp[b]]];
                d[h1[comp[b]] - h2[comp[b]]] += comp_set[comp[b]].size();
            }

            cant_sort.erase(comp[a]);
            cant_sort.erase(comp[b]);
            if (h1[comp[a]] != h2[comp[a]])
                cant_sort.insert(comp[a]);
            if (h1[comp[b]] != h2[comp[b]])
                cant_sort.insert(comp[b]);

            swap(y[a], y[b]);
            break;
        }
        case 2:
        {
            int64_t a, b;
            cin >> a >> b;
            a--, b--;

            if (comp[a] == comp[b])
                break;

            if (h1[comp[a]] != h2[comp[a]])
            {
                num_pairs -= comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
                d[h1[comp[a]] - h2[comp[a]]] -= comp_set[comp[a]].size();
            }
            if (h1[comp[b]] != h2[comp[b]])
            {
                num_pairs -= comp_set[comp[b]].size() * d[h2[comp[b]] - h1[comp[b]]];
                d[h1[comp[b]] - h2[comp[b]]] -= comp_set[comp[b]].size();
            }

            if (comp_set[comp[a]].size() < comp_set[comp[b]].size())
                swap(a, b);
            comp_set[comp[a]].insert(comp_set[comp[b]].begin(), comp_set[comp[b]].end());
            size_t const c = comp[b];
            for (size_t const &j : comp_set[c])
                comp[j] = comp[a];
            comp_set[c].clear();

            h1[comp[a]] = (h1[comp[a]] + h1[c]) % MOD;
            h2[comp[a]] = (h2[comp[a]] + h2[c]) % MOD;

            if (h1[comp[a]] != h2[comp[a]])
            {
                num_pairs += comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
                d[h1[comp[a]] - h2[comp[a]]] += comp_set[comp[a]].size();
            }

            cant_sort.erase(comp[a]);
            cant_sort.erase(c);

            if (h1[comp[a]] != h2[comp[a]])
                cant_sort.insert(comp[a]);
            break;
        }
        case 3:
        {
            cout << (cant_sort.empty() ? "DA" : "NE") << '\n';
            break;
        }
        case 4:
        {
            cout << num_pairs << '\n';
            break;
        }
        }
    }
}

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