제출 #1175839

#제출 시각아이디문제언어결과실행 시간메모리
1175839NomioZamjene (COCI16_zamjene)C++20
98 / 140
3082 ms130652 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1e9 + 7; const int maxn = 1e6 + 1; int sz[maxn], a[maxn], p[maxn], q[maxn]; ll P[maxn], Hsh = 20071030, h[maxn], H[maxn], ans = 0; map<ll, ll> m; void update(int t, ll val, int sze) { if(val != 0) ans += t * m[-val] * sze; m[val] += t * sze; } int find(int x) { if(a[x] == x) return x; else return a[x] = find(a[x]); } void unite(int u, int v) { u = find(u); v = find(v); if(u == v) return; if(sz[v] > sz[u]) swap(u, v); update(-1, (h[v] - H[v]), sz[v]); update(-1, (h[u] - H[u]), sz[u]); sz[u] += sz[v]; a[v] = u; h[u] += h[v]; H[u] += H[v]; update(1, (h[u] - H[u]), sz[u]); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, Q; cin >> n >> Q; P[0] = 1; for(int i = 1; i < maxn; i++) { P[i] = P[i - 1] * Hsh; P[i] %= mod; } for(int i = 1; i <= n; i++) { cin >> p[i]; q[i] = p[i]; a[i] = i; sz[i] = 1; } sort(q + 1, q + n + 1); for(int i = 1; i <= n; i++) { h[i] = P[p[i]]; H[i] = P[q[i]]; update(1, (h[i] - H[i]), 1); } while(Q--) { int t, u, v; cin >> t; if(t == 1) { cin >> u >> v; int U = find(u); int V = find(v); if(U == V) { swap(p[u], p[v]); continue; } update(-1, (h[U] - H[U]), sz[U]); update(-1, (h[V] - H[V]), sz[V]); h[U] -= P[p[u]]; h[V] -= P[p[v]]; swap(p[u], p[v]); h[U] += P[p[u]]; h[V] += P[p[v]]; update(1, (h[U] - H[U]), sz[U]); update(1, (h[V] - H[V]), sz[V]); } if(t == 2) { cin >> u >> v; unite(u, v); } if(t == 3) { cout << (m[0] == n ? "DA" : "NE") << '\n'; } if(t == 4) 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...