| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 49487 | minkank | 도로 건설 사업 (JOI13_construction) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef pair<int, ii> II;
#define x first
#define y second
const int N = 5e5 + 5;
struct Data {
int x, y, x2, y2;
};
int n, m, c, par[N];
long long f[N];
II qu[N * 2];
data p[N * 2];
vector<II> E;
bool cmp(data u, data v) {
return u.x < v.x;
}
void sweep() {
sort(p + 1, p + n + m + 1, cmp);
set<ii> s;
for(int i = 1; i <= n + m; ++i) {
if(p[i].x2 < 0) {
set<ii>::iterator it = s.lower_bound(ii(p[i].y, 0));
if(it != s.end() && (*it).x == p[i].y) {
int id = (*it).y;
E.push_back(II(p[i].x - p[id].x, ii(-p[id].x2, -p[i].x2)));
s.erase(it);
}
s.insert(ii(p[i].y, i));
}
else {
while(1) {
set<ii>::iterator it = s.lower_bound(ii(p[i].y, 0));
if(it == s.end() || (*it).x > p[i].y2) break;
s.erase(it);
}
}
}
}
void reverse() {
for(int i = 1; i <= n + m; ++i) {
swap(p[i].x, p[i].x2);
swap(p[i].y, p[i].y2);
}
}
int find(int u) {
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if(u == v) return false;
par[u] = v;
return true;
}
vector<ii> d;
bool bad(int l1, int l2, int l3) {
return 1LL * (d[l2].y - d[l1].y) * (d[l3].x - d[l2].x) > 1LL * (d[l3].y - d[l2].y) * (d[l2].x - d[l1].x);
}
void add(int a, long long b) {
d.push_back(ii(a, b));
while(d.size() >= 3 && !bad(d.size() - 1, d.size() - 2, d.size() - 3)) d.erase(d.end() - 2);
}
long long query(int x) {
int l = 0, r = d.size() - 1;
while(l != r) {
int mid = (l + r) >> 1;
if(1LL * d[mid].x * x + d[mid].y > 1LL * d[mid + 1].x * x + d[mid + 1].y) l = mid + 1;
else r = mid;
}
return 1LL * d[l].x * x + d[l].y;
}
long long ans[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> c;
for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y, p[i].x2 = p[i].y2 = -i;
for(int i = 1; i <= m; ++i) cin >> p[i + n].x >> p[i + n].y >> p[i + n].x >> p[i + n].y;
sweep();
reverse();
sweep();
sort(E.begin(), E.end());
int tot = 0;
vector<int> E2;
for(int i = 1; i <= n; ++i) par[i] = i;
for(int i = E.size() - 1; i >= 0; --i) {
int w = E[i].x, u = E[i].y.x, v = E[i].y.y;
if(join(u, v)) E2.push_back(w), tot += w;
}
int cnt = 0;
for(int i = 1; i <= n; ++i) if(find(i) == i) cnt++;
memset(f, 69, sizeof f);
f[cnt] = tot;
for(int i = 0; i < E2.size(); ++i) {
tot -= E2[i];
f[cnt + 1 + i] = tot;
}
for(int i = 1; i <= c; ++i) cin >> qu[i].y.x >> qu[i].x, qu[i].y.y = i;
for(int i = 1; i <= n; ++i) qu[i + c].x = i, qu[i + c].y.y = -1;
sort(qu + 1, qu + n + c + 1);
for(int i = 1; i <= n + c; ++i) {
if(qu[i].y.y < 0) {
add(qu[i].x, f[qu[i].x]);
}
else {
ans[qu[i].y.y] = query(qu[i].y.x);
}
}
for(int i = 1; i <= c; ++i) {
if(ans[i] > 1e18) ans[i] = -1;
cout << ans[i] << '\n';
}
}