Submission #94942

#TimeUsernameProblemLanguageResultExecution timeMemory
94942JustInCaseZamjene (COCI16_zamjene)C++17
84 / 140
1452 ms67320 KiB
#include <bits/stdc++.h> const int32_t BASE = 143; const int32_t MOD = 1e9 + 7; const int32_t MAX_N = 1e6; const int32_t MAX_P = 1e6; int32_t p[MAX_N + 5], q[MAX_N + 5]; int32_t basePowers[MAX_P + 5]; std::unordered_map< int32_t, int32_t > totalWithDiff; int64_t totalPairs; void Add(int32_t diff, int32_t cnt) { if(diff != 0) { totalPairs += (int64_t) cnt * totalWithDiff[-diff + MOD]; } totalWithDiff[diff] += cnt; } void Remove(int32_t diff, int32_t cnt) { if(diff != 0) { totalPairs -= (int64_t) cnt * totalWithDiff[-diff + MOD]; } totalWithDiff[diff] -= cnt; } class UnionFind { private: int32_t parents[MAX_N + 5], sizes[MAX_N + 5], sumsP[MAX_N + 5], sumsQ[MAX_N + 5]; public: void Init(int32_t pCntNodes) { for(int32_t i = 1; i <= pCntNodes; i++) { sumsP[i] = basePowers[p[i] - 1]; sumsQ[i] = basePowers[q[i] - 1]; parents[i] = i; sizes[i] = 1; int32_t diff = sumsP[i] - sumsQ[i]; if(diff < 0) { diff += MOD; } Add(diff, 1); } } int32_t Find(int32_t x) { if(x == parents[x]) { return x; } else { parents[x] = Find(parents[x]); return parents[x]; } } void Swap(int32_t x, int32_t y) { int32_t parX = Find(x); int32_t parY = Find(y); if(parX == parY) { std::swap(p[x], p[y]); return; } int32_t diffX = sumsP[parX] - sumsQ[parX]; if(diffX < 0) { diffX += MOD; } Remove(diffX, sizes[parX]); int32_t diffY = sumsP[parY] - sumsQ[parY]; if(diffY < 0) { diffY += MOD; } Remove(diffY, sizes[parY]); sumsP[parX] -= basePowers[p[x] - 1]; if(sumsP[parX] < 0) { sumsP[parX] += MOD; } sumsP[parX] = ((int64_t) sumsP[parX] + basePowers[p[y] - 1]) % MOD; sumsP[parY] -= basePowers[p[y] - 1]; if(sumsP[parY] < 0) { sumsP[parY] += MOD; } sumsP[parY] = ((int64_t) sumsP[parY] + basePowers[p[x] - 1]) % MOD; std::swap(p[x], p[y]); diffX = sumsP[parX] - sumsQ[parX]; if(diffX < 0) { diffX += MOD; } Add(diffX, sizes[parX]); diffY = sumsP[parY] - sumsQ[parY]; if(diffY < 0) { diffY += MOD; } Add(diffY, sizes[parY]); } void Union(int32_t x, int32_t y) { int32_t parX = Find(x); int32_t parY = Find(y); if(parX == parY) { return; } int32_t diffX = sumsP[parX] - sumsQ[parX]; if(diffX < 0) { diffX += MOD; } Remove(diffX, sizes[parX]); int32_t diffY = sumsP[parY] - sumsQ[parY]; if(diffY < 0) { diffY += MOD; } Remove(diffY, sizes[parY]); if(sizes[parX] <= sizes[parY]) { parents[parX] = parY; sizes[parY] += sizes[parX]; sumsP[parY] = ((int64_t) sumsP[parY] + sumsP[parX]) % MOD; sumsQ[parY] = ((int64_t) sumsQ[parY] + sumsQ[parX]) % MOD; diffY = sumsP[parY] - sumsQ[parY]; if(diffY < 0) { diffY += MOD; } Add(diffY, sizes[parY]); } else { parents[parY] = parX; sizes[parX] += sizes[parY]; sumsP[parX] = ((int64_t) sumsP[parX] + sumsP[parY]) % MOD; sumsQ[parX] = ((int64_t) sumsQ[parX] + sumsQ[parY]) % MOD; diffX = sumsP[parX] - sumsQ[parX]; if(diffX < 0) { diffX += MOD; } Add(diffX, sizes[parX]); } } }; UnionFind dsu; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int32_t n, m; std::cin >> n >> m; for(int32_t i = 1; i <= n; i++) { std::cin >> p[i]; q[i] = p[i]; } std::sort(q + 1, q + 1 + n); basePowers[0] = 1; for(int32_t i = 1; i < q[n]; i++) { basePowers[i] = ((int64_t) basePowers[i - 1] * BASE) % MOD; } dsu.Init(n); for(int32_t i = 0; i < m; i++) { int32_t t; std::cin >> t; if(t == 1) { int32_t a, b; std::cin >> a >> b; dsu.Swap(a, b); } else if(t == 2) { int32_t a, b; std::cin >> a >> b; dsu.Union(a, b); } else if(t == 3) { std::cout << (totalWithDiff[0] == n ? "DA" : "NE") << '\n'; } else { std::cout << totalPairs << '\n'; } } }
#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...