oj.uz

Submission #577251

# Submission time Handle Problem Language Result Execution time Memory
577251 2022-06-14T10:41:59 Z keta_tsimakuridze Zamjene (COCI16_zamjene) C++14
140 / 140
 4195 ms 215864 KB 
#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15956 KB Output is correct
2 Correct 18 ms 15956 KB Output is correct
3 Correct 19 ms 15944 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16036 KB Output is correct
2 Correct 19 ms 16040 KB Output is correct
3 Correct 16 ms 16040 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15956 KB Output is correct
2 Correct 18 ms 16084 KB Output is correct
3 Correct 18 ms 16084 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16052 KB Output is correct
2 Correct 16 ms 16044 KB Output is correct
3 Correct 17 ms 16044 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16084 KB Output is correct
2 Correct 22 ms 16064 KB Output is correct
3 Correct 19 ms 16212 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16852 KB Output is correct
2 Correct 23 ms 16876 KB Output is correct
3 Correct 22 ms 16936 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 23756 KB Output is correct
2 Correct 98 ms 25364 KB Output is correct
3 Correct 147 ms 28676 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 64608 KB Output is correct
2 Correct 3663 ms 155348 KB Output is correct
3 Correct 4195 ms 215864 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2027 ms 121376 KB Output is correct
2 Correct 3283 ms 153744 KB Output is correct
3 Correct 1440 ms 142636 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 87012 KB Output is correct
2 Correct 2358 ms 125848 KB Output is correct
3 Correct 1397 ms 142464 KB Output is correct