Submission #185645

#	Time	Username	Problem	Language	Result	Execution time	Memory
185645		ant101	Zamjene (COCI16_zamjene)	C++14	0 / 140	4883 ms	117556 KiB

zamjene

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 1000010;

ll P[MAXN], Q[MAXN];
ll N, M;
ll b = 31;
map<ll, ll> cc, m;

ll nodes = 0;
ll parent[MAXN];
ll nrank[MAXN];
ll hsp[MAXN];
ll hsq[MAXN];
ll ppow[MAXN];
ll sets = N;
ll sorted = 0;
ll ans = 0;
bool s = 0;

void updans(ll i, ll np, ll nq) {
    ll op = hsp[i], oq = hsq[i];
    if (s) {
        ans-=(m[op-oq]*(m[op-oq]-1))/2;
        ans-=(m[oq-op]*(m[oq-op]-1))/2;
        m[op-oq]--;
        m[oq-op]--;
    }
    ans-=(m[np-nq]*(m[np-nq]-1))/2;
    ans-=(m[nq-np]*(m[nq-np]-1))/2;
    m[np-nq]++;
    m[nq-np]++;
    if (s) {
        ans+=(m[op-oq]*(m[op-oq]-1))/2;
        ans+=(m[oq-op]*(m[oq-op]-1))/2;
    }
    ans+=(m[np-nq]*(m[np-nq]-1))/2;
    ans+=(m[nq-np]*(m[nq-np]-1))/2;
}

void create_set(ll t, ll a) {
    nodes++;
    parent[nodes] = nodes;
    nrank[nodes] = 0;
    hsp[nodes] = ppow[t];
    hsq[nodes] = ppow[a];
    updans(nodes, ppow[t], ppow[a]);
}

ll find_set(ll x) {
    if (parent[x] != x) {
        parent[x] = find_set(parent[x]);
    }
    return parent[x];
}

void merge_sets(ll x, ll y) {
    sets--;
    ll PX = find_set(x), PY = find_set(y);
    sorted-=((hsq[PX] == hsp[PX]) + (hsq[PY] == hsp[PY]));
    if (nrank[PX] > nrank[PY]) {
        parent[PY] = PX;
        updans(PX, add(hsp[PX], hsp[PY]), add(hsq[PX], hsq[PY]));
        add_self(hsp[PX], hsp[PY]);
        add_self(hsq[PX], hsq[PY]);
        sorted+=(hsq[PX] == hsp[PX]);
    } else {
        parent[PX] = PY;
        updans(PY, add(hsp[PX], hsp[PY]), add(hsq[PX], hsq[PY]));
        add_self(hsp[PY], hsp[PX]);
        add_self(hsq[PY], hsq[PX]);
        sorted+=(hsq[PY] == hsp[PY]);
    }
    if (nrank[PX] == nrank[PY]) {
        nrank[PY]++;
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (ll i = 1; i<=N; i++) {
        cin >> P[i];
        Q[i] = P[i];
    }
    sort(Q+1, Q+N+1);
    ll val = 1;
    ppow[1] = 1;
    for (ll i = 2; i<=N; i++) {
        ppow[i] = mul(ppow[i-1], b);
    }
    for (ll i = 1; i<=N; i++) {
        if (cc.find(Q[i]) == cc.end()) {
            cc[Q[i]] = val;
            val++;
        }
    }
    for (ll i = 1; i<=N; i++) {
        Q[i] = cc[Q[i]];
        P[i] = cc[P[i]];
    }
    for (ll i = 1; i<=N; i++) {
        create_set(P[i], Q[i]);
        sorted+=(P[i] == Q[i]);
        sets++;
    }
    s = 1;
    for (ll i = 0; i<M; i++) {
        ll type;
        cin >> type;
        if (type == 1) {
            ll A, B;
            cin >> A >> B;
            ll s1 = find_set(A), s2 = find_set(B);
            updans(s1, add(hsp[s1], sub(ppow[P[B]], ppow[P[A]])), hsq[s1]);
            updans(s2, add(hsp[s2], sub(ppow[P[A]], ppow[P[B]])), hsq[s2]);
            sorted-=(hsq[s1] == hsp[s1]) + (hsq[s2] == hsp[s2]);
            add_self(hsp[s1], sub(ppow[P[B]], ppow[P[A]]));
            add_self(hsp[s2], sub(ppow[P[A]], ppow[P[B]]));
            sorted+=(hsq[s1] == hsp[s1]) + (hsq[s2] == hsp[s2]);
        } else if (type == 2) {
            ll A, B;
            cin >> A >> B;
            ll s1 = find_set(A), s2 = find_set(B);
            if (s1 != s2) {
                merge_sets(s1, s2);
            }
        } else if (type == 3) {
            cout << (sorted == sets ? "DA" : "NE") << "\n";
        } else {
            ll sub = ((m[0]-1)*m[0]);
            cout << (ans-sub)/2 << "\n";
        }
    }
    return 0;
}

• 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