Submission #205996

#	Time	Username	Problem	Language	Result	Execution time	Memory
205996		MetB	Zamjene (COCI16_zamjene)	C++14	84 / 140	1962 ms	172308 KiB

zamjene

#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;

int 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);

	pw[0] = 1;

	for (int i = 1; i <= n; i++) {
		pw[i] = MOD2 * pw[i-1];
	}

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

	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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14