Submission #642179

#	Time	Username	Problem	Language	Result	Execution time	Memory
642179		lto5	Zamjene (COCI16_zamjene)	C++14	140 / 140	5356 ms	219704 KiB

zamjene

#include <bits/stdc++.h>
using namespace std;

#define int long long

mt19937_64 rd(time(NULL));
const int N = 1e6 + 5;
const int SWAP = 1;
const int ADD = 2;
const int SORT = 3;
const int COUNT = 4;

int n, q;
int a[N];
int sa[N];

long long hash_val[N];

int par[N];
long long h[N], sh[N];

set <int> violated;
map <long long, int> mp;

long long ans;

void read_input() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
}

void pre_ds() {
  for (int i = 0; i <= 1e6; i++) {
    hash_val[i] = uniform_int_distribution<long long>(0, 1e18)(rd);
  }
  for (int i = 0; i <= n; i++) {
    par[i] = -1;
  }
}

int root (int u) {
  return par[u] < 0 ? u : par[u] = root(par[u]);
}

bool violate (int u) {
  return h[u] != sh[u];
}

void del (int u) {
  u = root(u);
  if (!violate(u))
    return;
  violated.erase(u);
  mp[sh[u] - h[u]] -= -par[u];
  ans -= -par[u] * mp[h[u] - sh[u]];
}

void add (int u) {
  u = root(u);
  if (!violate(u))
    return;
  violated.insert(u);
  ans += -par[u] * mp[h[u] - sh[u]];
  mp[sh[u] - h[u]] += -par[u];
}

bool join (int u, int v) {
  u = root(u);
  v = root(v);

  if (u == v)
    return false;

  del(u);
  del(v);

  if (par[u] > par[v])
    swap(u, v);

  h[u] += h[v];
  sh[u] += sh[v];

  par[u] += par[v];
  par[v] = u;

  add(u);

  return true;
}

void build_dsu() {
  for (int i = 1; i <= n; i++) {
    sa[i] = a[i];
  }

  sort(sa + 1, sa + n + 1);

  for (int i = 1; i <= n; i++) {
    h[i] = hash_val[a[i]];
    sh[i] = hash_val[sa[i]];
    if (a[i] != sa[i]) {
      add(i);
    }
  }
}

void solve() {
  while (q--) {
    int t;
    cin >> t;

    if (t == SWAP) {
      int u, v;
      cin >> u >> v;

      int ru = root(u);
      int rv = root(v);

      if (ru == rv) {
        swap(a[u], a[v]);
        continue;
      }

      del(ru);
      del(rv);

      h[ru] -= hash_val[a[u]];
      h[rv] -= hash_val[a[v]];
      h[ru] += hash_val[a[v]];
      h[rv] += hash_val[a[u]];

      add(ru);
      add(rv);

      swap(a[u], a[v]);
    }

    else if (t == ADD) {
      int u, v;
      cin >> u >> v;
      join(u, v);
    }

    else if (t == SORT) {
      cout << (violated.size() == 0 ? "DA\n" : "NE\n");
    }

    else {
      cout << ans << "\n";
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

//  freopen("bb.cpp", "r", stdin);

  read_input();
  pre_ds();
  build_dsu();
  solve();

  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14