oj.uz

Submission #205995

# Submission time Handle Problem Language Result Execution time Memory
205995 2020-03-01T19:09:09 Z MetB Zamjene (COCI16_zamjene) C++14
98 / 140
 3080 ms 203796 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;

ll ans, cnt;

gp_hash_table <ll, int> 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);

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

	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';
		}
		cout << endl;
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 992 KB Output is correct
2 Correct 29 ms 1144 KB Output is correct
3 Correct 29 ms 1144 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 5196 KB Output is correct
2 Correct 274 ms 9468 KB Output is correct
3 Correct 287 ms 14012 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2583 ms 61356 KB Output is correct
2 Incorrect 2924 ms 171156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2861 ms 117600 KB Output is correct
2 Incorrect 3080 ms 203796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2698 ms 53464 KB Output is correct
2 Incorrect 2898 ms 117688 KB Output isn't correct
3 Halted 0 ms 0 KB -