#include <stdio.h>
#include <string.h>
#define N 200000
#define K 200000
#define M (N * 2)
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N + K * 2], yy[N + K * 2], n, k;
int uu[M], vv[M], ww[M], m;
int compare_xy(int i, int j) {
return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j];
}
int compare_w(int h1, int h2) {
return ww[h1] - ww[h2];
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int ok(int x1, int y1, int x2, int y2) {
int h;
for (h = 0; h < k; h++) {
int xl = max(xx[n + (h << 1 | 0)], x1), xr = min(xx[n + (h << 1 | 1)], x2);
int yl = max(yy[n + (h << 1 | 0)], y1), yr = min(yy[n + (h << 1 | 1)], y2);
if (xl <= xr && yl <= yr)
return 0;
}
return 1;
}
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
int main() {
static int ii[N], hh[M];
int m_, q, h, i, r, tmp;
long long sum;
scanf("%d%d%d", &n, &k, &q);
for (i = 0; i < n + k * 2; i++)
scanf("%d%d", &xx[i], &yy[i]);
for (r = 0; r < 2; r++) {
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_xy, sort(ii, 0, n);
for (i = 0; i + 1 < n; i++)
if (xx[ii[i]] == xx[ii[i + 1]] && ok(xx[ii[i]], xx[ii[i + 1]], yy[ii[i]], yy[ii[i + 1]]))
uu[m] = ii[i], vv[m] = ii[i + 1], ww[m] = yy[ii[i + 1]] - yy[ii[i]], m++;
for (i = 0; i < n + k * 2; i++)
tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
}
for (h = 0; h < m; h++)
hh[h] = h;
compare = compare_w, sort(hh, 0, m);
memset(ds, -1, n * sizeof *ds);
m_ = 0, sum = 0;
for (h = 0; h < m; h++)
if (join(uu[hh[h]], vv[hh[h]]))
hh[m_++] = hh[h], sum += ww[hh[h]];
m = m_;
while (q--) {
int w, c;
scanf("%d%d", &w, &c);
if (c < n - m)
printf("-1\n");
else {
long long ans;
ans = sum + (long long) (n - m) * w;
for (h = m - 1; h >= n - c && ww[hh[h]] > w; h--)
ans -= ww[hh[h]] - w;
printf("%lld\n", ans);
}
}
return 0;
}
Compilation message
construction.c: In function 'main':
construction.c:91:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d%d%d", &n, &k, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:93:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:116:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | scanf("%d%d", &w, &c);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
