#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL
#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Zamjene"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e6 + 7
#define int long long
using namespace std;
const ll HASH = 1234577;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, q;
int a[maxn], b[maxn];
ll Rnd[maxn];
struct DSU {
int lab[maxn], tplt;
ll S[maxn], Val;
map<ll, int> P;
void init() {
tplt = n;
fi(i, 1, n) Change(0, 1);
fi(i, 1, n) {
lab[i] = -1;
update(i, Rnd[a[i]] - Rnd[b[i]]);
}
}
void Change(ll val, ll w) {
if(val != 0) Val += P[-val] * w;
P[val] += w;
}
void update(int u, ll w) {
Change(S[u], lab[u]);
S[u] += w;
Change(S[u], -lab[u]);
}
bool good() { return P[0] == n; }
int get_rt(int u) {
return lab[u] < 0 ? u : lab[u] = get_rt(lab[u]);
}
void uni(int u, int v) {
int p = get_rt(u), q = get_rt(v); if(p == q) return;
if(lab[p] > lab[q]) swap(p, q);
--tplt;
ll Sum = S[p] + S[q];
update(q, -S[q]), update(p, -S[p]);
P[0] -= -(lab[p] + lab[q]);
lab[p] += lab[q], lab[q] = p;
S[p] = Sum, Change(S[p], -lab[p]);
}
} Dsu;
void solve()
{
cin >> n >> q;
fi(i, 1, n) cin >> a[i], b[i] = a[i];
sort(b + 1, b + 1 + n);
Dsu.init();
fi(i, 1, q) {
int type, x, y; cin >> type;
if(type <= 2) cin >> x >> y;
if(type == 1) {
int u = Dsu.get_rt(x), v = Dsu.get_rt(y);
Dsu.update(u, Rnd[a[y]] - Rnd[a[x]]);
Dsu.update(v, Rnd[a[x]] - Rnd[a[y]]);
swap(a[x], a[y]);
}
if(type == 2) {
Dsu.uni(x, y);
}
if(type == 3) {
cout << (Dsu.good() ? "DA\n" : "NE\n");
}
if(type == 4) {
cout << Dsu.Val << '\n';
}
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
Rnd[0] = 1;
fi(i, 1, maxn - 2) Rnd[i] = Rnd[i - 1] * HASH;
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
Compilation message
zamjene.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
118 | main()
| ^~~~
zamjene.cpp: In function 'int main()':
zamjene.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen(Neco".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zamjene.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(Neco".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8304 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8296 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8308 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8824 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
12628 KB |
Output is correct |
| 2 |
Correct |
59 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
102 ms |
17492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
580 ms |
49488 KB |
Output is correct |
| 2 |
Correct |
2794 ms |
141080 KB |
Output is correct |
| 3 |
Correct |
3371 ms |
192352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1314 ms |
92656 KB |
Output is correct |
| 2 |
Correct |
2188 ms |
114516 KB |
Output is correct |
| 3 |
Correct |
943 ms |
103344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
496 ms |
57864 KB |
Output is correct |
| 2 |
Correct |
1401 ms |
97620 KB |
Output is correct |
| 3 |
Correct |
922 ms |
103352 KB |
Output is correct |
