Submission #639949

#	Time	Username	Problem	Language	Result	Execution time	Memory
639949		GusterGoose27	Zamjene (COCI16_zamjene)	C++11	140 / 140	4302 ms	85832 KiB

zamjene

#include <bits/stdc++.h>

#define int ll

using namespace std;

typedef long long ll;

const int MAXN = 1e6;
const ll MOD = 2305843009213693951;

int perm[MAXN];
int psorted[MAXN];
ll coeffs[MAXN];
int n, q;
map<int, int> compress;
map<ll, int> hsh_count; // values that are here - values that should be here
int decompress[MAXN];
int uf[MAXN];
int sz[MAXN];
ll hshs[MAXN];
ll ans4 = 0;

int find(int i) {
	return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}

int get(ll k) {
	if (hsh_count.find(k) == hsh_count.end()) return 0;
	return hsh_count[k];
}

void ins(int rt) {
	ll hsh = hshs[rt];
	if (hsh != 0) ans4 += (ll) sz[rt]*get(MOD-hsh);
	hsh_count[hsh] += sz[rt];
}

void deins(int rt) {
	ll hsh = hshs[rt];
	hsh_count[hsh] -= sz[rt];
	if (hsh_count[hsh] == 0) hsh_count.erase(hsh);
	if (hsh != 0) ans4 -= (ll) sz[rt]*get(MOD-hsh);
}

bool good() {
	return (hsh_count.size() == 1 && hsh_count.begin()->first == 0);
}

ll mult(ll a, ll b) {
	unsigned __int128 r = a;
	r *= b;
	r %= MOD;
	return (ll) r;
}

void merge(int a, int b) {
	int ra = find(a);
	int rb = find(b);
	if (ra == rb) return;
	deins(ra);
	deins(rb);
	uf[ra] = rb;
	sz[rb] += sz[ra];
	hshs[rb] = (hshs[rb]+hshs[ra]) % MOD;
	ins(rb);
}

ll get_coeff(int i) {
	return coeffs[compress[perm[i]]];
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	default_random_engine gen;
	uniform_int_distribution<ll> dist(1, MOD-1);
	for (int i = 0; i < n; i++) {
		coeffs[i] = dist(gen)^dist(gen);
	}
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		perm[i] = x;
		psorted[i] = x;
	}
	sort(psorted, psorted+n);
	fill(uf, uf+n, -1);
	fill(sz, sz+n, 1);
	int t = 1;
	compress[psorted[0]] = 0;
	decompress[0] = psorted[0];
	for (int i = 1; i < n; i++) {
		if (psorted[i] == psorted[i-1]) continue;
		compress[psorted[i]] = t;
		decompress[t++] = psorted[i];
	}
	for (int i = 0; i < n; i++) {
		hshs[i] = (get_coeff(i)+MOD-coeffs[compress[psorted[i]]]) % MOD;
		ins(i);
	}
	for (int i = 0; i < q; i++) {
		int a, b; cin >> t;
		if (t == 1) {
			cin >> a >> b; a--; b--;
			int ra = find(a);
			int rb = find(b);
			if (ra == rb) {
				swap(perm[a], perm[b]);
				continue;
			}
			deins(ra);
			deins(rb);
			hshs[ra] += MOD-get_coeff(a);
			hshs[rb] += MOD-get_coeff(b);
			hshs[ra] %= MOD;
			hshs[rb] %= MOD;
			swap(perm[a], perm[b]);
			hshs[ra] += get_coeff(a);
			hshs[rb] += get_coeff(b);
			hshs[ra] %= MOD;
			hshs[rb] %= MOD;
			ins(ra);
			ins(rb);
		}
		if (t == 2) {
			cin >> a >> b; a--; b--;
			merge(a, b);
		}
		if (t == 3) {
			if (good()) cout << "DA\n";
			else cout << "NE\n";
		}
		if (t == 4) {
			cout << ans4 << "\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: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14