Submission #1175839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175839		Nomio	Zamjene (COCI16_zamjene)	C++20	98 / 140	3082 ms	130652 KiB

zamjene

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;
const int maxn = 1e6 + 1;
int sz[maxn], a[maxn], p[maxn], q[maxn];
ll P[maxn], Hsh = 20071030, h[maxn], H[maxn], ans = 0;
map<ll, ll> m;

void update(int t, ll val, int sze) {
	if(val != 0) ans += t * m[-val] * sze;
	m[val] += t * sze;  
}

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

void unite(int u, int v) {
	u = find(u);
	v = find(v);
	if(u == v) return;
	if(sz[v] > sz[u]) swap(u, v);
	update(-1, (h[v] - H[v]), sz[v]);
	update(-1, (h[u] - H[u]), sz[u]);
	sz[u] += sz[v];
	a[v] = u;
	h[u] += h[v];
	H[u] += H[v];
	update(1, (h[u] - H[u]), sz[u]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, Q;
	cin >> n >> Q;
	P[0] = 1;
	for(int i = 1; i < maxn; i++) {
		P[i] = P[i - 1] * Hsh;
		P[i] %= mod;
	}
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
		q[i] = p[i];
		a[i] = i;
		sz[i] = 1;
	}
	sort(q + 1, q + n + 1);
	for(int i = 1; i <= n; i++) {
		h[i] = P[p[i]];
		H[i] = P[q[i]];
		update(1, (h[i] - H[i]), 1);
	}
	while(Q--) {
		int t, u, v;
		cin >> t;
		if(t == 1) {
			cin >> u >> v;
			int U = find(u);
			int V = find(v);
			if(U == V) {
				swap(p[u], p[v]);
				continue;
			}
			update(-1, (h[U] - H[U]), sz[U]);
			update(-1, (h[V] - H[V]), sz[V]);
			h[U] -= P[p[u]];
			h[V] -= P[p[v]];
			swap(p[u], p[v]);
			h[U] += P[p[u]];
			h[V] += P[p[v]];
			update(1, (h[U] - H[U]), sz[U]);
			update(1, (h[V] - H[V]), sz[V]);
		} 
		if(t == 2) {
			cin >> u >> v;
			unite(u, v);
		}
		if(t == 3) {
			cout << (m[0] == n ? "DA" : "NE") << '\n';
		}
		if(t == 4) cout << ans << '\n';
	}
	return 0;
}

• 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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14