Submission #242579

#	Time	Username	Problem	Language	Result	Execution time	Memory
242579		VEGAnn	Zamjene (COCI16_zamjene)	C++14	140 / 140	1031 ms	71468 KiB

zamjene

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define PB push_back
#define ft first
#define sd second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
using namespace std;
using namespace __gnu_pbds;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1000100;
const int BIG = 1000100;
const int oo = 2e9;
gp_hash_table<ull, int> mem;
ull val[BIG], sum[N];
int a[N], pr[N], siz[N], n, q, srt[N];
ll ans = 0;

mt19937_64 rnd(chrono::system_clock().now().time_since_epoch().count());

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }

void delt(int xx){
    if (sum[xx] == 0) return;

    ull inv = ull(0) - sum[xx];

    if (mem.find(inv) != mem.end())
        ans -= 2 * mem[inv] * ll(siz[xx]);
}

void decv(int xx){
    if (sum[xx] == 0) return;

    mem[sum[xx]] -= siz[xx];

    if (mem[sum[xx]] == 0)
        mem.erase(sum[xx]);
}

void add(int xx){
    if (sum[xx] == 0) return;

    ull inv = ull(0) - sum[xx];

    if (mem.find(inv) != mem.end())
        ans += 2 * mem[inv] * ll(siz[xx]);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    for (int i = 1; i < BIG; i++)
        val[i] = rnd();

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        srt[i] = a[i];
        pr[i] = i;
        siz[i] = 1;
    }

    sort(srt, srt + n);

    for (int i = 0; i < n; i++)
        if (a[i] != srt[i]) {
            sum[i] = val[a[i]] - val[srt[i]];
            mem[sum[i]]++;
        }

    for (int i = 0; i < n; i++)
        if (a[i] != srt[i]) {
            ull cur = -val[a[i]] + val[srt[i]];

            if (mem.find(cur) != mem.end())
                ans += mem[cur];
        }

    for (int i = 0; i < n; i++)

    for (; q; q--){
        int tp; cin >> tp;

        if (tp == 1){
            int x, y; cin >> x >> y;
            x--; y--;

            swap(a[x], a[y]);

            int xx = get(x), yy = get(y);

            if (xx == yy) continue;

            delt(xx);
            delt(yy);

            decv(xx);
            decv(yy);

            if (sum[xx] != ull(0) && sum[xx] + sum[yy] == ull(0))
                ans += 2 * ll(siz[xx]) * ll(siz[yy]);

            sum[xx] -= val[a[y]] - val[a[x]];
            sum[yy] += val[a[y]] - val[a[x]];

            if (sum[yy] > 0) mem[sum[yy]] += siz[yy];
            if (sum[xx] > 0) mem[sum[xx]] += siz[xx];

            add(yy);
            add(xx);

            if (sum[xx] != ull(0) && sum[xx] + sum[yy] == ull(0))
                ans -= 2 * ll(siz[xx]) * ll(siz[yy]);
        } else if (tp == 2){
            int x, y; cin >> x >> y;
            x--; y--;

            int xx = get(x), yy = get(y);

            if (xx == yy) continue;

            delt(xx);
            delt(yy);

            decv(xx);
            decv(yy);

            if (sum[xx] != ull(0) && sum[xx] + sum[yy] == ull(0))
                ans += 2 * ll(siz[xx]) * ll(siz[yy]);

            pr[xx] = yy;
            siz[yy] += siz[xx];
            sum[yy] += sum[xx];

            if (sum[yy] > 0) mem[sum[yy]] += siz[yy];

            add(yy);
        } else if (tp == 3){
            cout << (sz(mem) == 0 ? "DA\n" : "NE\n");
        } else { //4
            cout << ans / 2 << '\n';
        }
    }

    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