oj.uz

Submission #639947

# Submission time Handle Problem Language Result Execution time Memory
639947 2022-09-12T19:20:36 Z GusterGoose27 Zamjene (COCI16_zamjene) C++11
84 / 140
 3997 ms 43960 KB 
#include <bits/stdc++.h>

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]]];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	default_random_engine gen;
	uniform_int_distribution<ll> dist(2, MOD-2);
	for (int i = 0; i < n; i++) {
		coeffs[i] = 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 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 #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 1 ms 340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 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 2 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 1 ms 340 KB Output is correct

Subtask #6
14.0 / 14.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3768 KB Output is correct
2 Correct 106 ms 4288 KB Output is correct
3 Incorrect 140 ms 5180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 20620 KB Output is correct
2 Incorrect 3997 ms 42940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1650 ms 43300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 36552 KB Output is correct
2 Incorrect 1864 ms 43960 KB Output isn't correct
3 Halted 0 ms 0 KB -