#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;
const ll P = 71;
const ll K = 213488;
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);
}
int main() {
fast
freopen("cowdate.out", "w", stdout);
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";
}
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:101:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen("cowdate.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
10704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
708 ms |
32744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1639 ms |
57888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
694 ms |
32196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
