Submission #735493

#TimeUsernameProblemLanguageResultExecution timeMemory
735493GrindMachineZamjene (COCI16_zamjene)C++17
70 / 140
6059 ms91152 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: https://bigprimes.org/ (for generating big prime MOD) sol idea: dsu + multiset hashing */ const ll MOD = 964863244005699737; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; struct DSU { vector<int> par, rankk, siz; vector<ll> hsh; map<ll, ll> hashes; ll cnt = 0; DSU() { } DSU(int n) { init(n); } void init(int n) { par = vector<int>(n + 1); rankk = vector<int>(n + 1); siz = vector<int>(n + 1); hsh = vector<ll>(n + 1); rep(i, n + 1) create(i); } void create(int u) { par[u] = u; rankk[u] = 0; siz[u] = 1; } int find(int u) { if (u == par[u]) return u; else return par[u] = find(par[u]); } bool same(int u, int v) { return find(u) == find(v); } void merge(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (rankk[u] == rankk[v]) rankk[u]++; if (rankk[u] < rankk[v]) swap(u, v); par[v] = u; siz[u] += siz[v]; // cnt -= siz[u] * hashes[MOD - hsh[u]]; // hashes[hsh[u]] -= siz[u]; // cnt -= siz[v] * hashes[MOD - hsh[v]]; // hashes[hsh[v]] -= siz[v]; // hsh[u] = (hsh[u] + hsh[v]) % MOD; // siz[u] += siz[v]; // cnt += siz[u] * hashes[MOD - hsh[u]]; // hashes[hsh[u]] += siz[u]; } }; void solve(int test_case) { ll n, q; cin >> n >> q; vector<ll> a(n + 5); rep1(i, n) cin >> a[i]; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<ll> dist(1, MOD - 1); auto b = a; sort(b.begin() + 1, b.begin() + n + 1); map<ll, ll> mp; rep1(i, n) { if (mp.count(a[i])) conts; mp[a[i]] = dist(rng); } DSU dsu(n + 5); rep1(i, n) { ll v = (mp[a[i]] - mp[b[i]] + MOD) % MOD; dsu.hsh[i] = v; dsu.cnt += dsu.hashes[MOD - v]; dsu.hashes[v]++; } while (q--) { ll t; cin >> t; if (t == 1) { ll u, v; cin >> u >> v; // if (dsu.same(u, v)) conts; swap(a[u], a[v]); // dsu.hashes.clear(); // dsu.cnt = 0; // vector<ll> here[n + 5]; // rep1(i, n) { // ll p = dsu.find(i); // here[p].pb(i); // } // rep1(p, n) { // if (here[p].empty()) conts; // dsu.hsh[p] = 0; // trav(i, here[p]) { // dsu.hsh[p] += mp[a[i]] - mp[b[i]]; // dsu.hsh[p] = (dsu.hsh[p] % MOD + MOD) % MOD; // } // ll siz = sz(here[p]); // dsu.cnt += siz * dsu.hashes[MOD - dsu.hsh[p]]; // dsu.hashes[dsu.hsh[p]] += siz; // } // ll pu = dsu.find(u), pv = dsu.find(v); // dsu.cnt -= dsu.siz[pu] * dsu.hashes[MOD - dsu.hsh[pu]]; // dsu.hashes[dsu.hsh[pu]] -= dsu.siz[pu]; // dsu.hsh[pu] += mp[a[v]] - mp[a[u]]; // dsu.hsh[pu] = (dsu.hsh[pu] % MOD + MOD) % MOD; // dsu.cnt += dsu.siz[pu] * dsu.hashes[MOD - dsu.hsh[pu]]; // dsu.hashes[dsu.hsh[pu]] += dsu.siz[pu]; // dsu.cnt -= dsu.siz[pv] * dsu.hashes[MOD - dsu.hsh[pv]]; // dsu.hashes[dsu.hsh[pv]] -= dsu.siz[pv]; // dsu.hsh[pv] += mp[a[u]] - mp[a[v]]; // dsu.hsh[pv] = (dsu.hsh[pv] % MOD + MOD) % MOD; // dsu.cnt += dsu.siz[pv] * dsu.hashes[MOD - dsu.hsh[pv]]; // dsu.hashes[dsu.hsh[pv]] += dsu.siz[pv]; // swap(a[u], a[v]); } else if (t == 2) { ll u, v; cin >> u >> v; dsu.merge(u, v); // dsu.hashes.clear(); // dsu.cnt = 0; // vector<ll> here[n + 5]; // rep1(i, n) { // ll p = dsu.find(i); // here[p].pb(i); // } // rep1(p, n) { // if (here[p].empty()) conts; // dsu.hsh[p] = 0; // trav(i, here[p]) { // dsu.hsh[p] += mp[a[i]] - mp[b[i]]; // dsu.hsh[p] = (dsu.hsh[p] % MOD + MOD) % MOD; // } // ll siz = sz(here[p]); // dsu.cnt += siz * dsu.hashes[MOD - dsu.hsh[p]]; // dsu.hashes[dsu.hsh[p]] += siz; // } } else if (t == 3) { bool ans = true; vector<ll> here[n + 5]; rep1(i, n) { ll p = dsu.find(i); here[p].pb(i); } rep1(p, n) { if (here[p].empty()) conts; vector<ll> v1, v2; trav(i, here[p]) { v1.pb(a[i]); v2.pb(b[i]); } sort(all(v1)), sort(all(v2)); if (v1 != v2) { ans = false; } } if (ans) cout << "DA" << endl; else cout << "NE" << endl; // if (dsu.hashes[0] == n) cout << "DA" << endl; // else cout << "NE" << endl; } else { vector<ll> here[n + 5]; rep1(i, n) { ll p = dsu.find(i); here[p].pb(i); } map<map<ll, ll>, ll> ma; ll ans = 0; rep1(p, n) { ll siz = sz(here[p]); if (!siz) conts; map<ll, ll> curr; trav(i, here[p]) { curr[a[i]]++; curr[b[i]]--; } vector<ll> toerase; trav(p, curr) { if (!p.ss) { toerase.pb(p.ff); } } trav(x, toerase) { curr.erase(x); } if (curr.empty()) conts; auto opp = curr; trav(p, opp) p.ss *= -1; ans += siz * ma[opp]; ma[curr] += siz; } cout << ans << endl; // map<ll, ll> ma; // ll ans = 0; // rep1(p, n) { // if (here[p].empty()) conts; // ll hsh = 0; // trav(i, here[p]) { // hsh += mp[a[i]] - mp[b[i]]; // hsh = (hsh % MOD + MOD) % MOD; // } // ans += dsu.siz[p] * ma[MOD - hsh]; // ma[hsh] += dsu.siz[p]; // } // cout << ans << endl; } } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } 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...