# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1242130 | tvgk | 도로 건설 사업 (JOI13_construction) | C++20 | 0 ms | 0 KiB |
for (int u = 0; u <= 1; u++)
{
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
vir.push_back(get<1>(a[i]));
for (int i = 1; i <= m; i++)
{
forbid[i] = {l[i].fi, i, 1};
forbid[i + m] = {r[i].fi + 1, i, -1};
vir.push_back(l[i].se);
vir.push_back(r[i].se);
}
sort(forbid + 1, forbid + 2 * m + 1);
sort(vir.begin(), vir.end());
vir.erase(unique(vir.begin(), vir.end()), vir.end());
int ctr = 1;
for (int i = 2; i <= n; i++)
{
while (ctr <= 2 * m && get<0>(forbid[ctr]) <= get<0>(a[i]))
{
int id = get<1>(forbid[ctr]);
Upd(l[id].se, r[id].se, get<2>(forbid[ctr]));
ctr++;
}
if (get<0>(a[i]) != get<0>(a[i - 1]))
continue;
if (!Get(get<1>(a[i - 1]), get<1>(a[i])))
Edge.push_back({get<1>(a[i]) - get<1>(a[i - 1]), get<2>(a[i - 1]), get<2>(a[i])});
}
for (int i = 1; i <= n; i++)
swap(get<0>(a[i]), get<1>(a[i]));
for (int i = 1; i <= m; i++)
{
swap(l[i].fi, l[i].se);
swap(r[i].fi, r[i].se);
}
Reset();
vir.clear();
}
sort(Edge.begin(), Edge.end());