Submission #990871

#	Time	Username	Problem	Language	Result	Execution time	Memory
990871		LOLOLO	Zamjene (COCI16_zamjene)	C++14	140 / 140	3524 ms	190896 KiB

zamjene

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e6 + 10;
map <ll, ll> cc;
int par[N], sz[N], a[N], b[N];
ll h1[N], h2[N], ans = 0, p[N];

void upd(ll t, ll val, ll sz) {
    if (val != 0) {
        ans += t * cc[-val] * sz;
    }

    cc[val] += t * sz;
}

int get(int a) {
    return par[a] ? get(par[a]) : a;
}

void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b)
        return;

    if (sz[a] < sz[b]) {
        swap(a, b);
    }

    upd(-1, h1[a] - h2[a], sz[a]);
    upd(-1, h1[b] - h2[b], sz[b]);
    sz[a] += sz[b];
    par[b] = a;
    h1[a] += h1[b];
    h2[a] += h2[b];
    upd(1, h1[a] - h2[a], sz[a]);
}

ll solve() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        sz[i] = 1;
        cin >> a[i];
        b[i] = a[i];
    }

    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++) {
        h1[i] = p[a[i]];
        h2[i] = p[b[i]];
        upd(1, h1[i] - h2[i], 1);
    }

    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            int x1 = get(x), y1 = get(y);
            if (x1 == y1) {
                swap(a[x], a[y]);
                continue;
            }

            upd(-1, h1[x1] - h2[x1], sz[x1]);
            upd(-1, h1[y1] - h2[y1], sz[y1]);
            h1[x1] -= p[a[x]];
            h1[y1] -= p[a[y]];
            
            swap(a[x], a[y]);
            h1[x1] += p[a[x]];
            h1[y1] += p[a[y]];
            upd(1, h1[x1] - h2[x1], sz[x1]);
            upd(1, h1[y1] - h2[y1], sz[y1]);
        }

        if (t == 2) {
            int x, y;
            cin >> x >> y;
            unite(x, y);
        }

        if (t == 3) {
            if (cc[0] == n) {
                cout << "DA\n";
            } else {
                cout << "NE\n";
            }
        }

        if (t == 4) {
            cout << ans << '\n';
        }
    }

    return 0;
}

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

    p[0] = 1;
    for (int i = 1; i < N; i++) {
        p[i] = p[i - 1] * 1234577;
    }

    int t = 1;
    //cin >> t;
 
    while (t--) {
        solve();
    }
 
    return 0;
} 

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 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