oj.uz

Submission #98378

# Submission time Handle Problem Language Result Execution time Memory
98378 2019-02-22T19:17:26 Z dalgerok Zamjene (COCI16_zamjene) C++17
140 / 140
 1511 ms 321368 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;



mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 5;



int n, m, a[N], b[N];

int p[N], sz[N];
long long ha[N], hb[N], P[N], ans;
struct super_hash{
    size_t operator()(unsigned long long x)const{
        static const unsigned long long fixedRand = rnd();
        return x ^ fixedRand;
    }
};

gp_hash_table < long long, int, super_hash > q;

int dsu_get(int v){
    return p[v] == v ? v : p[v] = dsu_get(p[v]);
}

inline void upd(int val, long long hsh, int sz){
    if(hsh != 0){
        ans += 1LL * val * sz * q[-hsh];
    }
    q[hsh] += val * sz;
}

inline void dsu_unite(int x, int y){
    x = dsu_get(x);
    y = dsu_get(y);
    if(x == y){
        return;
    }
    if(sz[x] < sz[y]){
        swap(x, y);
    }
    upd(-1, hb[x] - ha[x], sz[x]);
    upd(-1, hb[y] - ha[y], sz[y]);
    p[y] = x;
    ha[x] += ha[y];
    hb[x] += hb[y];
    sz[x] += sz[y];
    upd(+1, hb[x] - ha[x], sz[x]);
}

inline void dsu_upd(int val, int x, int y, int z){
    hb[x] += val * P[b[y]];
    ha[x] += val * P[z];
    sz[x] += val;
}

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] * 9988877;
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
        p[i] = i;
        sz[i] = 1;
    }
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++){
        hb[i] = P[b[i]];
        ha[i] = P[a[i]];
        upd(+1, hb[i] - ha[i], +1);
    }
    while(m--){
        int type;
        cin >> type;
        if(type == 1){
            int x, y;
            cin >> x >> y;
            int px = dsu_get(x),
                py = dsu_get(y);
            if(px == py){
                swap(a[x], a[y]);
                continue;
            }
            upd(-1, hb[px] - ha[px], sz[px]);
            upd(-1, hb[py] - ha[py], sz[py]);
            dsu_upd(-1, dsu_get(x), x, a[x]);
            dsu_upd(-1, dsu_get(y), y, a[y]);
            swap(a[x], a[y]);
            dsu_upd(+1, dsu_get(y), y, a[y]);
            dsu_upd(+1, dsu_get(x), x, a[x]);
            upd(+1, hb[py] - ha[py], sz[py]);
            upd(+1, hb[px] - ha[px], sz[px]);
        }
        else if(type == 2){
            int x, y;
            cin >> x >> y;
            dsu_unite(x, y);
        }
        else if(type == 3){
            cout << (q[0] == n ? "DA\n" : "NE\n");
        }
        else{
            cout << ans << "\n";
        }
    }
}

Compilation message

zamjene.cpp:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8448 KB Output is correct
2 Correct 10 ms 8320 KB Output is correct
3 Correct 11 ms 8440 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8832 KB Output is correct
2 Correct 14 ms 8704 KB Output is correct
3 Correct 16 ms 8952 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 11868 KB Output is correct
2 Correct 60 ms 13936 KB Output is correct
3 Correct 86 ms 20964 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 45512 KB Output is correct
2 Correct 1346 ms 174196 KB Output is correct
3 Correct 1511 ms 321368 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 116712 KB Output is correct
2 Correct 1087 ms 116216 KB Output is correct
3 Correct 982 ms 115764 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 47672 KB Output is correct
2 Correct 972 ms 116424 KB Output is correct
3 Correct 979 ms 115748 KB Output is correct