Submission #577251

#	Time	Username	Problem	Language	Result	Execution time	Memory
577251		keta_tsimakuridze	Zamjene (COCI16_zamjene)	C++14	140 / 140	4195 ms	215864 KiB

zamjene

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 1e6 + 5, mod = 100000002181, mod2 = 100000003787; //!
int t, ans = 0, h[N], p[N], par[N], a[N], b[N], cn, sz[N], h2[N], p2[N];
map<pii,int> m;
void get(int h, int h2, int p, int p2, int t, int sz) {
	if(h == p) return;
	
	cn += t;
	if(t == -1)	m[{(p - h + mod)% mod, (p2 - h2 + mod2)% mod2}]  += sz * t;
	ans = ans + t * m[{(h - p + mod)% mod, (h2 - p2 + mod2)% mod2}] * sz;
	if(t == 1)m[{(p - h + mod)% mod, (p2 - h2 + mod2)% mod2}]  += sz * t;
}
int find(int x) {
	return (par[x] == x ? x : par[x] = find(par[x]));
}
void merge(int u, int v) {
	u = find(u); v = find(v);
	if(u == v) return;
	par[v] = u;		
	get(h[u], h2[u], p[u], p2[u], -1, sz[u]); 
	get(h[v], h2[v], p[v], p2[v], -1, sz[v]);
	sz[u] += sz[v];
	h[u] = (h[u] + h[v]) % mod;
	h2[u] = (h2[u] + h2[v]) % mod2;
	p[u] = (p[u] + p[v]) % mod;	
	p2[u] = (p2[u] + p2[v]) % mod2;	
	get(h[u], h2[u], p[u], p2[u], 1, sz[u]);

}
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, q;
	cin >> n >> q;
	int prm = 1000579, prm2 = 1001797;
	vector<int> P(N), P2(N);
	P[0] = P2[0] = 1;
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; sz[i] = 1;

		b[i] = a[i];
	}
	for(int i = 1; i <= N - 5; i++)		
	P[i] = P[i - 1] * prm % mod,
	P2[i] = P2[i - 1] * prm2 % mod2;
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++) {
		h[i] = a[i] * P[a[i]] % mod;
		h2[i] = a[i] * P2[a[i]] % mod2;
		p[i] = b[i] * P[b[i]] % mod; 
		p2[i] = b[i] * P2[b[i]] % mod2; 
		get(h[i], h2[i], p[i], p2[i], 1, sz[i]);
		par[i] = i;
	} 
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int i, j; cin >> i >> j;
			if(find(i) == find(j)) {
				swap(a[i], a[j]);
				
			} else  {
				swap(a[i], a[j]);
				
				get(h[find(i)], h2[find(i)], p[find(i)], p2[find(i)], -1, sz[find(i)]);
				
				get(h[find(j)], h2[find(j)], p[find(j)], p2[find(j)], -1, sz[find(j)]);
			
				h[find(j)] = (h[find(j)] - a[i] * P[a[i]] % mod + a[j] * P[a[j]] % mod + mod) % mod; 
				h2[find(j)] = (h2[find(j)] - a[i] * P2[a[i]] % mod2 + a[j] * P2[a[j]] % mod2 + mod2) % mod2; 
				h[find(i) ] = (h[find(i)] + a[i] * P[a[i]] % mod - a[j] * P[a[j]] % mod + mod) % mod;
				h2[find(i)] = (h2[find(i)] + a[i] * P2[a[i]] % mod2 - a[j] * P2[a[j]] % mod2 + mod2) % mod2;
				get(h[find(i)], h2[find(i)], p[find(i)], p2[find(i)], 1, sz[find(i)]);
				get(h[find(j)], h2[find(j)], p[find(j)], p2[find(j)], 1, sz[find(j)]);				
			} 
			continue;
		}
		if(t == 2) {
			int x, y;
			cin >> x >> y;
			
			merge(x, y);
			continue;
		}
		else if(t == 3) {
			cout << (!cn ? "DA" : "NE") << endl; 
		} else cout << ans << endl;
	}
}

Compilation message (stderr)

zamjene.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~

• 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