oj.uz

Submission #990871

# Submission time Handle Problem Language Result Execution time Memory
990871 2024-05-31T16:53:46 Z LOLOLO Zamjene (COCI16_zamjene) C++14
140 / 140
 3524 ms 190896 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 17064 KB Output is correct
3 Correct 3 ms 17040 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16984 KB Output is correct
2 Correct 6 ms 16984 KB Output is correct
3 Correct 6 ms 17244 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 19804 KB Output is correct
2 Correct 53 ms 21340 KB Output is correct
3 Correct 104 ms 24656 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 49256 KB Output is correct
2 Correct 2849 ms 140116 KB Output is correct
3 Correct 3524 ms 190896 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1334 ms 81208 KB Output is correct
2 Correct 2247 ms 102228 KB Output is correct
3 Correct 945 ms 89940 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 46932 KB Output is correct
2 Correct 1436 ms 86100 KB Output is correct
3 Correct 959 ms 89936 KB Output is correct