Submission #419274

#TimeUsernameProblemLanguageResultExecution timeMemory
419274SirCovidThe19thZamjene (COCI16_zamjene)C++14
98 / 140
3749 ms130988 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mx = 1e6+5; int n, q; int vals[mx], sorted[mx]; int par[mx], sz[mx]; ll hsh[mx], cnP[mx], cnQ[mx]; unordered_map<ll, ll> diff; ll cnt; int find(int node) { return (node == par[node]) ? node : par[node] = find(par[node]); } void upd(int i, int change){ change *= sz[i]; if (cnP[i] != cnQ[i]) cnt += diff[cnQ[i]-cnP[i]]*(ll)change; diff[cnP[i]-cnQ[i]] += change; } void merge(int a, int b){ a = find(a); b = find(b); if (a == b) return; if (sz[a] > sz[b]) swap(a, b); upd(a, -1); upd(b, -1); par[a] = b; sz[b] += sz[a]; cnP[b] += cnP[a]; cnQ[b] += cnQ[a]; upd(b, 1); } void Swap(int a, int b){ int parA = find(a), parB = find(b); upd(parA, -1); upd(parB, -1); cnP[parA] = (cnP[parA]-hsh[vals[a]]+hsh[vals[b]]); cnP[parB] = (cnP[parB]-hsh[vals[b]]+hsh[vals[a]]); upd(parA, 1); upd(parB, 1); swap(vals[a], vals[b]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); cin >> n >> q; for (int i = 0; i < n; i++){ cin >> vals[i]; vals[i]--; sorted[i] = vals[i]; hsh[i] = rng(); } sort(sorted, sorted+n); iota(par, par+n, 0); fill(sz, sz+n, 1); for (int i = 0; i < n; i++){ cnP[i] = hsh[vals[i]], cnQ[i] = hsh[sorted[i]]; diff[cnP[i]-cnQ[i]]++; } map<int, bool> visited; for (int i = 0; i < n; i++){ if (cnP[i] != cnQ[i] and !visited[cnP[i]-cnQ[i]]){ cnt += diff[cnP[i]-cnQ[i]]*diff[cnQ[i]-cnP[i]]; visited[cnP[i]-cnQ[i]] = true; visited[cnQ[i]-cnP[i]] = true; } } for (int i = 0; i < q; i++){ int t, a, b; cin >> t; if (t <= 2) { cin >> a >> b; a--; b--; } if (t == 1) Swap(a, b); if (t == 2) merge(a, b); if (t == 3) cout<<((diff[0] == n) ? "DA":"NE")<<endl; if (t == 4) cout<<cnt<<endl; } }
#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...