oj.uz

Submission #878956

# Submission time Handle Problem Language Result Execution time Memory
878956 2023-11-25T18:31:21 Z serifefedartar Zamjene (COCI16_zamjene) C++17
140 / 140
 5414 ms 195432 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 = 1322131;
const ll P2 = 14342481;
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;
}

pair<ll,ll> Hash(ll x) {
	return {expo(x, P), expo(x, P2)};
}

int ans4 = 0;
int not_equal = 0;
map<pair<ll,ll>,int> cnt;
int par[MAXN], sz[MAXN];
pair<int,int> 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].f || st[a].s)
		ans4 -= cnt[{MOD - st[a].f, MOD - st[a].s}] * sz[a];
	if (st[b].f || st[b].s)
		ans4 -= cnt[{MOD - st[b].f, MOD - st[b].s}] * sz[b];
	ans4 += ((((st[a].f + st[b].f) % MOD) == 0 && ((st[a].s + st[b].s) % MOD) == 0 && (st[a].f != 0 || st[a].s != 0)) ? sz[a] * sz[b] : 0);
	cnt[st[a]] -= sz[a];
	cnt[st[b]] -= sz[b];
	sz[a] += sz[b];

	not_equal -= (st[a].f != 0 || st[a].s != 0) + (st[b].f != 0 || st[b].s != 0);
	st[a] = {(st[a].f + st[b].f) % MOD, (st[a].s + st[b].s) % MOD};

	cnt[st[a]] += sz[a];
	if (st[a].f != 0 || st[b].f != 0)
		ans4 += cnt[{MOD - st[a].f, MOD - st[a].s}] * sz[a];
	not_equal += (st[a].f != 0 || st[a].s != 0);
}

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

	if (st[parA].f || st[parA].s)
		ans4 -= cnt[{MOD - st[parA].f, MOD - st[parA].s}] * sz[parA];
	if ((st[parB].f || st[parB].s) && parB != parA)
		ans4 -= cnt[{MOD - st[parB].f, MOD - st[parB].s}] * sz[parB];
	if (parB != parA) 
		ans4 += ((((st[parA].f + st[parB].f) % MOD) == 0 && ((st[parA].s + st[parB].s) % MOD) == 0 && (st[parA].f != 0 || st[parA].s != 0)) ? sz[parA] * sz[parB] : 0);

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

	not_equal -= (st[parA].f != 0 || st[parA].s != 0) + (st[parB].f != 0 || st[parB].s != 0);
	st[parA] = {(st[parA].f - Hash(A[a]).f + Hash(A[b]).f) % MOD, (st[parA].s - Hash(A[a]).s + Hash(A[b]).s) % MOD};
	st[parB] = {(st[parB].f - Hash(A[b]).f + Hash(A[a]).f) % MOD, (st[parB].s - Hash(A[b]).s + Hash(A[a]).s) % MOD};
	if (st[parA].f < 0) st[parA].f += MOD;
	if (st[parA].s < 0) st[parA].s += MOD;
	if (st[parB].f < 0) st[parB].f += MOD;
	if (st[parB].s < 0) st[parB].s += MOD;

	cnt[st[parA]] += sz[parA];
	if (parA != parB)
		cnt[st[parB]] += sz[parB];
	if (st[parA].f || st[parA].s)
		ans4 += cnt[{MOD - st[parA].f, MOD - st[parA].s}] * sz[parA];
	if ((st[parB].f || st[parB].s) && parB != parA)
		ans4 += cnt[{MOD - st[parB].f, MOD - st[parB].s}] * sz[parB];
	if (parB != parA)
		ans4 -= ((((st[parA].f + st[parB].f) % MOD) == 0 && ((st[parA].s + st[parB].s) % MOD) == 0 && (st[parA].f != 0 || st[parA].s != 0)) ? sz[parA] * sz[parB] : 0);
	swap(A[a], A[b]);
	not_equal += (st[parA].f != 0 || st[parA].s != 0) + (st[parB].f != 0 || st[parB].s != 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;
		pair<int,int> H1 = Hash(A[i]);
		pair<int,int> H2 = Hash(B[i]);
		st[i] = {H1.f - H2.f, H1.s - H2.s};
		sz[i] = 1;
		if (st[i].f < 0)
			st[i].f += MOD;
		if (st[i].s < 0)
			st[i].s += MOD;
		cnt[st[i]]++;
		not_equal += (st[i].f != 0 || st[i].s != 0);
	}

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

	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 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 2 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 4440 KB Output is correct
2 Correct 2 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 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 #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4940 KB Output is correct
2 Correct 12 ms 5028 KB Output is correct
3 Correct 11 ms 5040 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 8732 KB Output is correct
2 Correct 147 ms 10288 KB Output is correct
3 Correct 162 ms 13556 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 45248 KB Output is correct
2 Correct 4543 ms 135284 KB Output is correct
3 Correct 5414 ms 195432 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2249 ms 89204 KB Output is correct
2 Correct 3674 ms 122620 KB Output is correct
3 Correct 2000 ms 111296 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 54800 KB Output is correct
2 Correct 2576 ms 93904 KB Output is correct
3 Correct 1969 ms 111140 KB Output is correct