Submission #626811

#TimeUsernameProblemLanguageResultExecution timeMemory
626811MilosMilutinovicZamjene (COCI16_zamjene)C++14
0 / 140
1849 ms74320 KiB
/** * author: wxhtzdy * created: 11.08.2022 22:00:57 **/ #include <bits/stdc++.h> using namespace std; class dsu { public: vector<int> p; int n; dsu(int _n) : n(_n) { p.resize(n); iota(p.begin(), p.end(), 0); } inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); } inline bool unite(int x, int y) { x = get(x); y = get(y); if (x != y) { p[x] = y; return true; } return false; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> c0(n); for (int i = 0; i < n; i++) { cin >> c0[i]; } auto c1 = c0; sort(c1.begin(), c1.end()); vector<long long> pw(1, 1); const long long BASE = 77777; for (int i = 1; i <= c1.back(); i++) { pw.push_back((pw.back() * BASE) % 998244353); } dsu d(n); vector<long long> f0(n); vector<long long> f1(n); map<long long, long long> cnt; long long ans = 0; auto Add = [&](int x, long long c) { if (x != 0) { ans += cnt[-x] * 1LL * c; } cnt[x] += c; }; auto Remove = [&](int x, long long c) { if (x != 0) { ans -= cnt[-x] * 1LL * c; } cnt[x] -= c; }; for (int i = 0; i < n; i++) { f0[i] = pw[c0[i]]; f1[i] = pw[c1[i]]; Add(f0[i] - f1[i], +1); } vector<int> sz(n, 1); while (q--) { int op; cin >> op; if (op == 1) { int a, b; cin >> a >> b; --a; --b; if (d.get(a) == d.get(b)) { swap(c0[a], c0[b]); continue; } int na = a; int nb = b; a = d.get(a); b = d.get(b); Remove(f0[a] - f1[a], sz[a]); Remove(f0[b] - f1[b], sz[b]); f0[a] -= pw[c0[a]]; f0[a] += pw[c0[b]]; f0[b] -= pw[c0[b]]; f0[b] += pw[c0[a]]; Add(f0[a] - f1[a], sz[a]); Add(f0[b] - f1[b], sz[b]); swap(c0[na], c0[nb]); } else if (op == 2) { int a, b; cin >> a >> b; --a; --b; a = d.get(a); b = d.get(b); if (a == b) { continue; } Remove(f0[a] - f1[a], sz[a]); Remove(f0[b] - f1[b], sz[b]); d.unite(a, b); if (d.get(a) != a) { assert(b == d.get(a)); swap(a, b); } f0[a] += f0[b]; f1[a] += f1[b]; sz[a] += sz[b]; Add(f0[a] - f1[a], sz[a]); } else if (op == 3) { cout << (cnt[0] == n ? "DA" : "NE") << '\n'; } else { cout << ans << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...