oj.uz

Submission #243265

# Submission time Handle Problem Language Result Execution time Memory
243265 2020-06-30T16:24:46 Z Vimmer Zamjene (COCI16_zamjene) C++14
84 / 140
 2140 ms 151660 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;

unordered_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) 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 13 ms 8832 KB Output is correct
2 Correct 15 ms 8960 KB Output is correct
3 Correct 14 ms 8960 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 14456 KB Output is correct
2 Correct 76 ms 15796 KB Output is correct
3 Correct 105 ms 17792 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 52968 KB Output is correct
2 Correct 1775 ms 111268 KB Output is correct
3 Correct 2140 ms 151660 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1336 ms 96108 KB Output is correct
2 Correct 1703 ms 119712 KB Output is correct
3 Correct 991 ms 102252 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 72436 KB Output is correct
2 Correct 1351 ms 98800 KB Output is correct
3 Correct 994 ms 102252 KB Output is correct