oj.uz

Submission #243270

# Submission time Handle Problem Language Result Execution time Memory
243270 2020-06-30T16:36:02 Z Vimmer Zamjene (COCI16_zamjene) C++14
140 / 140
 5495 ms 189480 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 1000001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll HASH = 7261523, id[N], pr[N], hsh[N], need[N], kol, p[N], a[N], sz[N];

ll ans = 0;

map <ll, ll> mp;

void make(ll x)
{
    pr[x] = x;

    sz[x] = 1;

    hsh[x] = p[id[x]];

    need[x] = p[a[x]];

    if (need[x] != hsh[x])
    {
        kol++;

        ans += mp[hsh[x] - need[x]] * sz[x];

        mp[-(hsh[x] - need[x])] += sz[x];
    }
}

ll fnd(ll x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}

void link(ll a, ll b)
{
    a = fnd(a); b = fnd(b);

    if (a == b) return;

    pr[b] = a;

    if (hsh[b] != need[b])
    {
            kol--;

            mp[-(hsh[b] - need[b])] -= sz[b];

            ans -= sz[b] * mp[hsh[b] - need[b]];
    }

    if (hsh[a] != need[a])
    {
            kol--;

            mp[-(hsh[a] - need[a])] -= sz[a];

            ans -= sz[a] * mp[hsh[a] - need[a]];
    }

    hsh[a] = (hsh[a] + hsh[b]);

    need[a] = (need[a] + need[b]);

    sz[a] += sz[b];

    if (hsh[a] != need[a])
    {
            kol++;

            ans += sz[a] * mp[hsh[a] - need[a]];

            mp[-(hsh[a] - need[a])] += sz[a];
    }
}

void swaper(ll l, ll r)
{
    ll x = fnd(l), y = fnd(r);

    if (x == y) {swap(a[l], a[r]); return;}

    if (hsh[x] != need[x])
        {
            kol--;

            mp[-(hsh[x] - need[x])] -= sz[x];

            ans -= mp[hsh[x] - need[x]] * sz[x];
        }

    if (hsh[y] != need[y])
        {
            kol--;

            mp[-(hsh[y] - need[y])] -= sz[y];

            ans -= mp[hsh[y] - need[y]] * sz[y];
        }

    hsh[x] = (hsh[x] - p[id[l]]);
    hsh[y] = (hsh[y] - p[id[r]]);

    need[x] = (need[x] - p[a[l]]);
    need[y] = (need[y] - p[a[r]]);

    swap(a[l], a[r]);

    need[x] = (need[x] + p[a[l]]);
    need[y] = (need[y] + p[a[r]]);

    hsh[x] = (hsh[x] + p[id[l]]);
    hsh[y] = (hsh[y] + p[id[r]]);

    if (hsh[x] != need[x])
    {
            kol++;

            mp[-(hsh[x] - need[x])] += sz[x];

            ans += mp[hsh[x] - need[x]] * sz[x];
    }

    if (hsh[y] != need[y])
    {
            kol++;

            mp[-(hsh[y] - need[y])] += sz[y];

            ans += mp[hsh[y] - need[y]] * sz[y];
    }
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, q;

    p[0] = 1;

    for (ll i = 1; i < N; i++) p[i] = p[i - 1] * HASH;

    cin >> n >> q;

    for (ll i = 0; i < n; i++) {cin >> a[i]; id[i] = a[i];}

    sort(id, id + n);

    for (ll i = 0; i < n; i++) make(i);

    for (; q > 0; q--)
    {
        ll tp, l, r;

        cin >> tp;

        if (tp == 1) {cin >> l >> r; l--; r--; swaper(l, r); continue;}

        if (tp == 2) {cin >> l >> r; l--; r--; link(l, r); continue;}

        if (tp == 3) {if (kol == 0) cout << "DA" << '\n'; else cout << "NE" << '\n'; continue;}

        cout << ans << '\n';
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 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 8192 KB Output is correct
2 Correct 10 ms 8192 KB Output is correct
3 Correct 10 ms 8320 KB Output is correct

Subtask #5
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 8320 KB Output is correct

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13304 KB Output is correct
2 Correct 107 ms 14968 KB Output is correct
3 Correct 171 ms 18168 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 48088 KB Output is correct
2 Correct 4730 ms 138732 KB Output is correct
3 Correct 5495 ms 189480 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2515 ms 96892 KB Output is correct
2 Correct 4125 ms 118024 KB Output is correct
3 Correct 1838 ms 105720 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1151 ms 62840 KB Output is correct
2 Correct 2826 ms 102048 KB Output is correct
3 Correct 1768 ms 105828 KB Output is correct