oj.uz

Submission #642186

# Submission time Handle Problem Language Result Execution time Memory
642186 2022-09-18T15:57:46 Z lto5 Zamjene (COCI16_zamjene) C++14
140 / 140
 4258 ms 183080 KB 
#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];

int cnt;
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;
  cnt--;
  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;
  cnt++;
  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 << (cnt == 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8148 KB Output is correct
2 Correct 14 ms 8096 KB Output is correct
3 Correct 14 ms 8132 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8148 KB Output is correct
2 Correct 12 ms 8148 KB Output is correct
3 Correct 12 ms 8272 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8228 KB Output is correct
2 Correct 13 ms 8144 KB Output is correct
3 Correct 13 ms 8288 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8660 KB Output is correct
2 Correct 17 ms 8612 KB Output is correct
3 Correct 18 ms 8664 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11768 KB Output is correct
2 Correct 81 ms 13172 KB Output is correct
3 Correct 118 ms 16356 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 38412 KB Output is correct
2 Correct 3653 ms 128784 KB Output is correct
3 Correct 4258 ms 183080 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1667 ms 77548 KB Output is correct
2 Correct 2965 ms 98444 KB Output is correct
3 Correct 1221 ms 86212 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 43272 KB Output is correct
2 Correct 1955 ms 82568 KB Output is correct
3 Correct 1228 ms 86416 KB Output is correct