oj.uz

Submission #878946

# Submission time Handle Problem Language Result Execution time Memory
878946 2023-11-25T16:57:42 Z serifefedartar Zamjene (COCI16_zamjene) C++17
84 / 140
 1803 ms 86340 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 + 100;
#define int long long

const ll P = 73;
const ll K = 998224353;
vector<int> A, B;
ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

ll Hash(ll x) {
	return expo((x + K) % MOD, P);
}

int ans4 = 0;
int not_equal = 0;
map<int,int> cnt;
int par[MAXN], sz[MAXN], st[MAXN];
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return ;
	if (sz[b] > sz[a])
		swap(a, b);
	par[b] = a;

	if (st[a])
		ans4 -= cnt[MOD - st[a]] * sz[a];
	if (st[b])
		ans4 -= cnt[MOD - st[b]] * sz[b];
	ans4 += ((((st[a] + st[b]) % MOD) == 0 && st[a] != 0) ? sz[a] * sz[b] : 0);
	cnt[st[a]] -= sz[a];
	cnt[st[b]] -= sz[b];
	sz[a] += sz[b];

	not_equal -= (st[a] != 0) + (st[b] != 0);
	st[a] = (st[a] + st[b]) % MOD;

	cnt[st[a]] += sz[a];
	if (st[a] != 0)
		ans4 += cnt[MOD - st[a]] * sz[a];
	not_equal += (st[a] != 0);
}

void swp(int a, int b) {
	int parA = find(a);
	int parB = find(b);

	if (st[parA])
		ans4 -= cnt[MOD - st[parA]] * sz[parA];
	if (st[parB] && parB != parA)
		ans4 -= cnt[MOD - st[parB]] * sz[parB];
	ans4 += ((((st[parA] + st[parB]) % MOD) == 0 && st[parA] != 0) ? sz[parA] * sz[parB] : 0);

	cnt[st[parA]] -= sz[parA];
	if (parA != parB)
		cnt[st[parB]] -= sz[parB];

	not_equal -= (st[parA] != 0) + (st[parB] != 0);
	st[parA] = (st[parA] - Hash(A[a]) + Hash(A[b])) % MOD;
	st[parB] = (st[parB] - Hash(A[b]) + Hash(A[a])) % MOD;
	if (st[parA] < 0) st[parA] += MOD;
	if (st[parB] < 0) st[parB] += MOD;

	cnt[st[parA]] += sz[parA];
	if (parA != parB)
		cnt[st[parB]] += sz[parB];
	if (st[parA])
		ans4 += cnt[MOD - st[parA]] * sz[parA];
	if (st[parB] && parB != parA)
		ans4 += cnt[MOD - st[parB]] * sz[parB];
	ans4 -= ((((st[parA] + st[parB]) % MOD) == 0 && st[parA] != 0) ? sz[parA] * sz[parB] : 0);
	swap(A[a], A[b]);
	not_equal += (st[parA] != 0) + (st[parB] != 0);
}

signed main() {
	fast
	int N, Q;
	cin >> N >> Q; 

	A = vector<int>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		B.push_back(A[i]);
	}
	sort(B.begin(), B.end(), greater<int>());
	B.push_back(0);
	reverse(B.begin(), B.end());

	for (int i = 1; i <= N; i++) {
		par[i] = i;
		st[i] = Hash(A[i]) - Hash(B[i]);
		sz[i] = 1;
		if (st[i] < 0)
			st[i] += MOD;
		cnt[st[i]]++;
		not_equal += (st[i] != 0);
	}

	for (auto u : cnt) {
		if (u.f >= MOD - u.f)
			continue;
		ans4 += u.s * cnt[MOD - u.f];
	}

	while (Q--) {
		int T, A, B;
		cin >> T;
		if (T == 1) {
			cin >> A >> B;
			swp(A, B);
		} else if (T == 2) {
			cin >> A >> B;
			unite(A, B);
		} else if (T == 3)
			cout << (not_equal == 0 ? "DA\n" : "NE\n");
		else
			cout << ans4 << "\n";
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 10700 KB Output is correct
2 Incorrect 69 ms 12236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 46992 KB Output is correct
2 Incorrect 1803 ms 86340 KB Output isn't correct
3 Halted 0 ms 0 KB -