oj.uz

Submission #205996

# Submission time Handle Problem Language Result Execution time Memory
205996 2020-03-01T19:12:28 Z MetB Zamjene (COCI16_zamjene) C++14
84 / 140
 1962 ms 172308 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 1000001
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int p[N], sz[N], n, pw[N];

ll ans, cnt;

gp_hash_table <ll, ll> ht;
ll h[N];

void change (int x, ll d) {
	if (h[x]) ans -= sz[x] * ht[-h[x]];
	ht[h[x]] -= sz[x];
	if (!d) return;
	h[x] += d;

	if (h[x]) ans += sz[x] * ht[-h[x]];
	ht[h[x]] += sz[x];
}

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

void unite (int a, int b) {
	a = find (a), b = find (b);
	if (a == b) return;

	p[b] = a;

	if (h[a]) ans -= sz[a] * ht[-h[a]];
	ht[h[a]] -= sz[a];

	h[a] += h[b];
	sz[a] += sz[b];

	if (h[a]) ans += sz[a] * ht[-h[a]];
	ht[h[a]] += sz[a];

	change (b, 0);
	cnt--;
}

ll q, a[N], s[N], rn[N];

int main () {
	ios::sync_with_stdio (0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> q;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		s[i] = a[i];
	}

	sort (s, s + n);

	pw[0] = 1;

	for (int i = 1; i <= n; i++) {
		pw[i] = MOD2 * pw[i-1];
	}

	for (int i = 1; i <= n; i++) {
		//rn[i] = uniform_int_distribution<ll>(0, (1LL << 32))(rng);
		rn[i] = pw[i];
	}

	for (int i = 0; i < n; i++) {
		p[i] = i, sz[i] = 1;
		h[i] = rn[a[i]] - rn[s[i]];
		ht[h[i]]++;
	}

	for (int i = 0; i < n; i++) {
		if (h[i]) ans += ht[-h[i]];
	}

	ans /= 2;

	cnt = n;

	for (int i = 0; i < q; i++) {
		int t, x, y;
		cin >> t;

		if (t == 2) {
			cin >> x >> y;
			x--, y--;
			unite (x, y);
		}

		if (t == 1) {
			cin >> x >> y;
			x--, y--;
			int px = find (x), py = find (y);

			change (px, -rn[a[x]]);
			change (py, -rn[a[y]]);

			swap (a[x], a[y]);
			
			change (px, rn[a[x]]);
			change (py, rn[a[y]]);
		}

		if (t == 3) {
			if (ht[0] == n) cout << "DA\n";
			else cout << "NE\n";
		}

		if (t == 4) {
			cout << ans << '\n';
		}
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 636 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 5436 KB Output is correct
2 Correct 167 ms 9832 KB Output is correct
3 Incorrect 169 ms 14304 KB Output isn't correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1612 ms 62480 KB Output is correct
2 Incorrect 1962 ms 172308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 56224 KB Output is correct
2 Incorrect 1833 ms 120516 KB Output isn't correct
3 Halted 0 ms 0 KB -