| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 738456 |
2023-05-08T19:35:14 Z |
finn__ |
Zamjene (COCI16_zamjene) |
C++17 |
|
4536 ms |
418916 KB |
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 1000001;
constexpr __int128_t B = 1000000007, Mod = (1LL << 61) - 1;
__int128_t p[N];
int32_t a[N], dsu[N];
map<uint32_t, uint64_t> def[N], over[N];
__int128_t defh[N], overh[N];
map<int64_t, unordered_map<int64_t, uint64_t>> mp;
size_t good_count, pair_count;
int32_t repr(int32_t u) { return dsu[u] < 0 ? u : dsu[u] = repr(dsu[u]); }
void dsu_merge(int32_t u, int32_t v)
{
u = repr(u);
v = repr(v);
dsu[u] += dsu[v];
dsu[v] = u;
}
bool dsu_same_set(int32_t u, int32_t v) { return repr(u) == repr(v); }
int32_t dsu_set_size(int32_t u) { return -dsu[repr(u)]; }
void erase_cloud(size_t i)
{
if (!defh[i])
{
good_count--;
return;
}
auto it = mp.find(overh[i]);
if (it != mp.end())
{
auto jt = it->second.find(defh[i]);
if (jt != it->second.end())
pair_count -= dsu_set_size(i) * jt->second;
}
mp[defh[i]][overh[i]] -= dsu_set_size(i);
}
void insert_cloud(size_t i)
{
if (!defh[i])
{
good_count++;
return;
}
auto it = mp.find(overh[i]);
if (it != mp.end())
{
auto jt = it->second.find(defh[i]);
if (jt != it->second.end())
pair_count += dsu_set_size(i) * jt->second;
}
mp[defh[i]][overh[i]] += dsu_set_size(i);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
p[0] = 1;
for (size_t i = 1; i < N; ++i)
p[i] = (p[i - 1] * B) % Mod;
size_t n, q;
cin >> n >> q;
for (size_t i = 0; i < n; ++i)
cin >> a[i], dsu[i] = a[i];
sort(dsu, dsu + n);
size_t num_components = n;
for (size_t i = 0; i < n; ++i)
{
if (a[i] == dsu[i])
good_count++;
else
{
def[i][dsu[i]] = 1;
over[i][a[i]] = 1;
defh[i] = p[dsu[i]];
overh[i] = p[a[i]];
auto it = mp.find(overh[i]);
if (it != mp.end())
{
auto jt = it->second.find(defh[i]);
if (jt != it->second.end())
pair_count += jt->second;
}
mp[defh[i]][overh[i]]++;
}
}
memset(dsu, 255, sizeof dsu);
while (q--)
{
uint32_t t;
cin >> t;
if (t == 1)
{
uint32_t i, j;
cin >> i >> j;
--i, --j;
if (repr(i) == repr(j))
continue;
erase_cloud(repr(i));
erase_cloud(repr(j));
for (auto const &k : {i, j})
{
auto const l = repr(k);
auto it = over[l].find(a[k]);
if (it != over[l].end() && it->second)
{
overh[l] = (overh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
it->second--;
overh[l] = (overh[l] + p[a[k]] * it->second) % Mod;
}
else
{
it = def[l].find(a[k]);
if (it != def[l].end())
defh[l] = (defh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
def[l][a[k]]++;
defh[l] = (defh[l] + p[a[k]] * def[l][a[k]]) % Mod;
}
}
swap(a[i], a[j]);
for (auto const &k : {i, j})
{
auto const l = repr(k);
auto it = def[l].find(a[k]);
if (it != def[l].end() && it->second)
{
defh[l] = (defh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
it->second--;
defh[l] = (defh[l] + p[a[k]] * it->second) % Mod;
}
else
{
it = over[l].find(a[k]);
if (it != over[l].end())
overh[l] = (overh[l] - (p[a[k]] * it->second) % Mod + Mod) % Mod;
over[l][a[k]]++;
overh[l] = (overh[l] + p[a[k]] * over[l][a[k]]) % Mod;
}
}
insert_cloud(repr(i));
insert_cloud(repr(j));
}
else if (t == 2)
{
uint32_t i, j;
cin >> i >> j;
--i, --j;
if (dsu_same_set(i, j))
continue;
--num_components;
if (dsu_set_size(i) < dsu_set_size(j))
swap(i, j);
i = repr(i);
j = repr(j);
erase_cloud(i);
erase_cloud(j);
for (auto &[elem, cnt] : over[j])
{
auto it = def[i].find(elem);
if (it != def[i].end())
{
defh[i] = (defh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
uint32_t x = min(it->second, cnt);
it->second -= x;
cnt -= x;
defh[i] = (defh[i] + p[elem] * it->second) % Mod;
}
}
for (auto &[elem, cnt] : def[j])
{
auto it = over[i].find(elem);
if (it != over[i].end())
{
overh[i] = (overh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
uint32_t x = min(it->second, cnt);
it->second -= x;
cnt -= x;
overh[i] = (overh[i] + p[elem] * it->second) % Mod;
}
}
for (auto &[elem, cnt] : over[j])
{
auto it = over[i].find(elem);
if (it != over[i].end())
overh[i] = (overh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
over[i][elem] += cnt;
overh[i] = (overh[i] + p[elem] * over[i][elem]) % Mod;
}
for (auto &[elem, cnt] : def[j])
{
auto it = def[i].find(elem);
if (it != def[i].end())
defh[i] = (defh[i] - (p[elem] * it->second) % Mod + Mod) % Mod;
def[i][elem] += cnt;
defh[i] = (defh[i] + p[elem] * def[i][elem]) % Mod;
}
dsu_merge(i, j);
insert_cloud(i);
}
else if (t == 3)
{
cout << (good_count == num_components ? "DA" : "NE") << '\n';
}
else
{
cout << pair_count << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
113868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
113816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
113884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
113868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
113924 KB |
Output is correct |
| 2 |
Correct |
59 ms |
114028 KB |
Output is correct |
| 3 |
Correct |
59 ms |
114120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
114980 KB |
Output is correct |
| 2 |
Correct |
64 ms |
115092 KB |
Output is correct |
| 3 |
Correct |
73 ms |
115060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
133164 KB |
Output is correct |
| 2 |
Correct |
193 ms |
137564 KB |
Output is correct |
| 3 |
Correct |
261 ms |
142432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1762 ms |
260972 KB |
Output is correct |
| 2 |
Correct |
4083 ms |
386660 KB |
Output is correct |
| 3 |
Correct |
4536 ms |
404804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2242 ms |
377244 KB |
Output is correct |
| 2 |
Correct |
3402 ms |
418916 KB |
Output is correct |
| 3 |
Correct |
1806 ms |
262940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1656 ms |
331844 KB |
Output is correct |
| 2 |
Correct |
2883 ms |
387132 KB |
Output is correct |
| 3 |
Correct |
1800 ms |
262956 KB |
Output is correct |
