oj.uz

Submission #242579

# Submission time Handle Problem Language Result Execution time Memory
242579 2020-06-28T10:03:16 Z VEGAnn Zamjene (COCI16_zamjene) C++14
140 / 140
 1031 ms 71468 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8192 KB Output is correct
2 Correct 16 ms 8192 KB Output is correct
3 Correct 17 ms 8192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 17 ms 8192 KB Output is correct
3 Correct 16 ms 8192 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 16 ms 8192 KB Output is correct
3 Correct 16 ms 8192 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 16 ms 8192 KB Output is correct
3 Correct 16 ms 8320 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8192 KB Output is correct
2 Correct 16 ms 8320 KB Output is correct
3 Correct 18 ms 8320 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8576 KB Output is correct
2 Correct 19 ms 8576 KB Output is correct
3 Correct 19 ms 8704 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 11000 KB Output is correct
2 Correct 58 ms 12020 KB Output is correct
3 Correct 64 ms 13168 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 25708 KB Output is correct
2 Correct 866 ms 59304 KB Output is correct
3 Correct 1031 ms 58668 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 53320 KB Output is correct
2 Correct 796 ms 71468 KB Output is correct
3 Correct 621 ms 71172 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 37608 KB Output is correct
2 Correct 702 ms 53308 KB Output is correct
3 Correct 647 ms 71188 KB Output is correct