oj.uz

Submission #676346

# Submission time Handle Problem Language Result Execution time Memory
676346 2022-12-30T12:44:24 Z finn__ Zamjene (COCI16_zamjene) C++17
0 / 140
 5143 ms 226444 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 8276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 9700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 25764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3700 ms 109192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5143 ms 226444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3998 ms 189220 KB Output isn't correct
2 Halted 0 ms 0 KB -