oj.uz

Submission #639951

# Submission time Handle Problem Language Result Execution time Memory
639951 2022-09-12T19:32:37 Z GusterGoose27 Zamjene (COCI16_zamjene) C++11
140 / 140
 4732 ms 73208 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 852 KB Output is correct
2 Correct 6 ms 864 KB Output is correct
3 Correct 7 ms 948 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5344 KB Output is correct
2 Correct 90 ms 5896 KB Output is correct
3 Correct 164 ms 6844 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 28488 KB Output is correct
2 Correct 4252 ms 50796 KB Output is correct
3 Correct 4732 ms 57656 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1737 ms 59056 KB Output is correct
2 Correct 4013 ms 73208 KB Output is correct
3 Correct 1773 ms 71588 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 52252 KB Output is correct
2 Correct 1872 ms 59684 KB Output is correct
3 Correct 1780 ms 71920 KB Output is correct