#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> II;
struct Point {
int x, y, i;
Point() {};
Point(int x, int y, int i): x(x), y(y), i(i) {};
};
struct Edge {
int u, v, w;
Edge() {};
Edge(int u, int v, int w): u(u), v(v), w(w) {};
bool operator < (const Edge &E) const {
return w < E.w;
}
};
const int N = (int) 2e5 + 10;
int n, m, k, q, x[N], y[N];
Point P[N];
Edge E[N * 4];
bool mark[N * 4];
int p[N];
int com_count[N];
LL sum_edges[N];
int Root(int u) {
if (p[u] < 0) return u;
return p[u] = Root(p[u]);
}
int Merge(int u, int v) {
u = Root(u);
v = Root(v);
if (u == v) return 0;
if (p[u] > p[v]) swap(u, v);
p[u] += p[v]; p[v] = u;
return 1;
}
bool cmp_by_X(Point A, Point B) { return A.x < B.x || (A.x == B.x && A.y < B.y); }
bool cmp_by_Y(Point A, Point B) { return A.y < B.y || (A.y == B.y && A.x < B.x); }
void InitEdge() {
sort(P + 1, P + 1 + n, cmp_by_X);
for (int i = 1; i <= n; ++i) {
int j = i;
while (j < n && P[j + 1].x == P[i].x) j++;
for (int t = i; t <= j - 1; ++t) {
int w = abs(P[t].x - P[t + 1].x) + abs(P[t].y - P[t + 1].y);
E[++m] = Edge(P[t].i, P[t + 1].i, w);
}
i = j;
}
sort(P + 1, P + 1 + n, cmp_by_Y);
for (int i = 1; i <= n; ++i) {
int j = i;
while (j < n && P[j + 1].y == P[i].y) j++;
for (int t = i; t <= j - 1; ++t) {
int w = abs(P[t].x - P[t + 1].x) + abs(P[t].y - P[t + 1].y);
E[++m] = Edge(P[t].i, P[t + 1].i, w);
}
i = j;
}
sort(E + 1, E + 1 + m);
}
int main() {
scanf("%d%d%d", &n, &k, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &y[i]);
P[i] = Point(x[i], y[i], i);
}
InitEdge();
for (int i = 1; i <= m; ++i) mark[i] = true;
for (int i = 1; i <= k; ++i) {
int x1, y1; scanf("%d%d", &x1, &y1);
int x2, y2; scanf("%d%d", &x2, &y2);
for (int j = 1; j <= m; ++j) {
int u = E[j].u;
int v = E[j].v;
if (x[u] == x[v] && x1 <= x[u] && x[u] <= x2) {
if (max(y[u], y1) <= min(y[v], y2)) mark[j] = false;
}
if (y[u] == y[v] && y1 <= y[u] && y[u] <= y2) {
if (max(x[u], x1) <= min(x[v], x2)) mark[j] = false;
}
}
}
for (int i = 1; i <= n; ++i) p[i] = -1; com_count[0] = n;
for (int i = 1; i <= m; ++i) {
int u = E[i].u;
int v = E[i].v;
com_count[i] = com_count[i - 1];
sum_edges[i] = sum_edges[i - 1];
if (mark[i] && Merge(u, v)) {
com_count[i] -= 1;
sum_edges[i] += E[i].w;
}
}
while (q--) {
int a, b; scanf("%d%d", &a, &b);
int l = 1, r = m, f = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (com_count[mid] <= b) {
f = mid;
r = mid - 1;
}
else l = mid + 1;
}
LL ans = (LL) 1e18;
if (f != -1) ans = min(ans, sum_edges[f] + (LL) a * b);
l = 1; r = m; f = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (E[mid].w <= a) {
f = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (com_count[f] <= b) ans = min(ans, sum_edges[f] + (LL) a * com_count[f]);
if (ans == (LL) 1e18) ans = -1;
printf("%lld\n", ans);
}
return 0;
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &q);
^
construction.cpp:74:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x[i], &y[i]);
^
construction.cpp:81:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x1, y1; scanf("%d%d", &x1, &y1);
^
construction.cpp:82:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x2, y2; scanf("%d%d", &x2, &y2);
^
construction.cpp:108:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
373 ms |
19212 KB |
Output is correct |
| 2 |
Correct |
639 ms |
19212 KB |
Output is correct |
| 3 |
Correct |
583 ms |
19212 KB |
Output is correct |
| 4 |
Memory limit exceeded |
1099 ms |
262144 KB |
Memory limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5000 ms |
19212 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
999 ms |
19212 KB |
Output is correct |
| 2 |
Correct |
1213 ms |
19212 KB |
Output is correct |
| 3 |
Correct |
1002 ms |
19212 KB |
Output is correct |
| 4 |
Memory limit exceeded |
1029 ms |
262144 KB |
Memory limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5000 ms |
19212 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
