oj.uz

Submission #642181

# Submission time Handle Problem Language Result Execution time Memory
642181 2022-09-18T15:50:35 Z lto5 Zamjene (COCI16_zamjene) C++14
126 / 140
 6000 ms 150208 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];

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8196 KB Output is correct
2 Correct 18 ms 8140 KB Output is correct
3 Correct 12 ms 8148 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8148 KB Output is correct
2 Correct 17 ms 8188 KB Output is correct
3 Correct 21 ms 8144 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8228 KB Output is correct
2 Correct 21 ms 8276 KB Output is correct
3 Correct 21 ms 8308 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8708 KB Output is correct
2 Correct 20 ms 8792 KB Output is correct
3 Correct 19 ms 8860 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 15684 KB Output is correct
2 Correct 265 ms 17908 KB Output is correct
3 Correct 377 ms 21096 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2758 ms 54324 KB Output is correct
2 Execution timed out 6038 ms 150208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3813 ms 120576 KB Output is correct
2 Correct 5031 ms 142600 KB Output is correct
3 Correct 2161 ms 102424 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2345 ms 83052 KB Output is correct
2 Correct 4178 ms 125724 KB Output is correct
3 Correct 2149 ms 102592 KB Output is correct