oj.uz

Submission #205998

# Submission time Handle Problem Language Result Execution time Memory
205998 2020-03-01T19:20:10 Z MetB Zamjene (COCI16_zamjene) C++14
140 / 140
 2249 ms 332384 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 1000001
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

ll p[N], sz[N], n, pw[N];

ll ans, cnt;

gp_hash_table <ll, ll> ht;
ll h[N];

void change (int x, ll d) {
	if (h[x]) ans -= sz[x] * ht[-h[x]];
	ht[h[x]] -= sz[x];
	if (!d) return;
	h[x] += d;

	if (h[x]) ans += sz[x] * ht[-h[x]];
	ht[h[x]] += sz[x];
}

int find (int x) {
	if (p[x] == x) return x;
	return p[x] = find (p[x]);
}

void unite (int a, int b) {
	a = find (a), b = find (b);
	if (a == b) return;

	p[b] = a;

	if (h[a]) ans -= sz[a] * ht[-h[a]];
	ht[h[a]] -= sz[a];

	h[a] += h[b];
	sz[a] += sz[b];

	if (h[a]) ans += sz[a] * ht[-h[a]];
	ht[h[a]] += sz[a];

	change (b, 0);
	cnt--;
}

ll q, a[N], s[N], rn[N];

int main () {
	ios::sync_with_stdio (0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> q;

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

	sort (s, s + n);

	for (int i = 1; i <= n; i++) {
		rn[i] = uniform_int_distribution<ll>(0, (1LL << 62))(rng);
	}

	for (int i = 0; i < n; i++) {
		p[i] = i, sz[i] = 1;
		h[i] = rn[a[i]] - rn[s[i]];
		ht[h[i]]++;
	}

	for (int i = 0; i < n; i++) {
		if (h[i]) ans += ht[-h[i]];
	}

	ans /= 2;

	cnt = n;

	for (int i = 0; i < q; i++) {
		int t, x, y;
		cin >> t;

		if (t == 2) {
			cin >> x >> y;
			x--, y--;
			unite (x, y);
		}

		if (t == 1) {
			cin >> x >> y;
			x--, y--;
			int px = find (x), py = find (y);

			change (px, -rn[a[x]]);
			change (py, -rn[a[y]]);

			swap (a[x], a[y]);
			
			change (px, rn[a[x]]);
			change (py, rn[a[y]]);
		}

		if (t == 3) {
			if (ht[0] == n) cout << "DA\n";
			else cout << "NE\n";
		}

		if (t == 4) {
			cout << ans << '\n';
		}
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 500 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 508 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 632 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1144 KB Output is correct
2 Correct 18 ms 1272 KB Output is correct
3 Correct 20 ms 1272 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 5812 KB Output is correct
2 Correct 167 ms 10220 KB Output is correct
3 Correct 187 ms 14672 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1621 ms 64236 KB Output is correct
2 Correct 1950 ms 174376 KB Output is correct
3 Correct 2249 ms 332384 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 125216 KB Output is correct
2 Correct 2041 ms 198732 KB Output is correct
3 Correct 1786 ms 137208 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1634 ms 61016 KB Output is correct
2 Correct 1849 ms 125000 KB Output is correct
3 Correct 1813 ms 137428 KB Output is correct