#include <bits/stdc++.h>
using namespace std;
#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;
const int INF = 1e9;
struct tree {
static const int L = 1 << 19;
ll T[L*2], C[L*2];
void add_node(int rt, int x) {
T[rt] += x;
C[rt] += x;
}
void pushdown(int rt) {
if(C[rt]) {
add_node(rt*2, C[rt]);
add_node(rt*2+1, C[rt]);
C[rt] = 0;
}
}
void update(int s, int e, int x, int rt = 1, int l = 0, int r = L-1) {
if(s <= l && r <= e) {
add_node(rt, x);
return;
}
pushdown(rt);
int m = (l + r) >> 1;
if(s <= m) update(s, e, x, rt*2, l, m);
if(m < e) update(s, e, x, rt*2+1, m+1, r);
T[rt] = max(T[rt*2], T[rt*2+1]);
}
int Read(int s, int e, int rt = 1, int l = 0, int r = L-1) {
if(s <= l && r <= e) return T[rt];
pushdown(rt);
int m = (l + r) >> 1, res = 0;
if(s <= m) res = max(res, Read(s, e, rt*2, l, m));
if(m < e) res = max(res, Read(s, e, rt*2+1, m+1, r));
return res;
}
void init() {
memset(T, 0, sizeof T);
memset(C, 0, sizeof C);
}
} tree;
int N, M, C;
struct rect {
int x1, y1, x2, y2;
} R[200020];
struct point {
int x, y, id;
} P[200020];
struct event {
int x, y1, y2, i1, i2;
};
vector <t3> E;
void Do(vector <int> &vy) {
sort(P+1, P+1+N, [](point a, point b) { return tie(a.x, a.y) < tie(b.x, b.y); });
vector <event> V;
for(int i=1;i<N;i++) if(P[i].x == P[i+1].x) {
V.pb({P[i].x, P[i].y, P[i+1].y, P[i].id, P[i+1].id});
}
for(int i=1;i<=M;i++) {
V.pb({R[i].x1, R[i].y1, R[i].y2, -1, 0});
V.pb({R[i].x2, R[i].y1, R[i].y2, INF, 0});
}
sort(all(V), [](const event &a, const event &b) { return tie(a.x, a.i1) < tie(b.x, b.i1); });
tree.init();
for(auto &[x, y1, y2, i1, i2] : V) {
if(i1 == -1) tree.update(y1, y2, 1);
else if(i1 == INF) tree.update(y1, y2, -1);
else {
int v = tree.Read(y1, y2);
if(v == 0) E.pb({vy[y2] - vy[y1], i1, i2});
}
}
}
int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int main() {
scanf("%d%d%d", &N, &M, &C);
vector <int> vx, vy;
for(int i=1;i<=N;i++) {
int x, y; scanf("%d%d", &x, &y);
P[i] = {x, y, i};
vx.pb(x); vy.pb(y);
}
for(int i=1;i<=M;i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
R[i] = {x1, y1, x2, y2};
vx.pb(x1), vx.pb(x2);
vy.pb(y1), vy.pb(y2);
}
sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
auto fix = [](vector <int> &a, int &b) {
b = (int)(lower_bound(all(a), b) - a.begin());
};
for(int i=1;i<=N;i++) fix(vx, P[i].x), fix(vy, P[i].y);
for(int i=1;i<=M;i++) {
fix(vx, R[i].x1), fix(vx, R[i].x2);
fix(vy, R[i].y1), fix(vy, R[i].y2);
}
rep(v, 2) {
Do(v == 0 ? vy : vx);
for(int i=1;i<=M;i++) {
swap(R[i].x1, R[i].y1);
swap(R[i].x2, R[i].y2);
}
for(int i=1;i<=N;i++) swap(P[i].x, P[i].y);
}
sort(all(E));
for(int i=1;i<=N;i++) pp[i] = i;
vector <int> V;
vector <ll> SV;
for(auto &[l, x, y] : E) {
int px = Find(x), py = Find(y);
if(px != py) V.pb(l);
}
int lv = szz(V);
SV.resize(lv);
rep(i, lv) SV[i] = (i ? SV[i-1] : 0) + V[i];
rep(c, C) {
int b, h;
scanf("%d%d", &b, &h);
if(N - lv > h) puts("-1");
else {
int cnt = (int)(lower_bound(all(V), b) - V.begin());
cnt = max(cnt, N - h);
printf("%lld\n", (ll)(N - cnt) * b + (cnt ? SV[cnt-1] : 0));
}
}
return 0;
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
93 | scanf("%d%d%d", &N, &M, &C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
96 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
construction.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
102 | scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
138 | scanf("%d%d", &b, &h);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
17888 KB |
Output is correct |
| 2 |
Correct |
346 ms |
30716 KB |
Output is correct |
| 3 |
Correct |
352 ms |
30784 KB |
Output is correct |
| 4 |
Incorrect |
360 ms |
37844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
17888 KB |
Output is correct |
| 2 |
Correct |
346 ms |
30716 KB |
Output is correct |
| 3 |
Correct |
352 ms |
30784 KB |
Output is correct |
| 4 |
Incorrect |
360 ms |
37844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
17888 KB |
Output is correct |
| 2 |
Correct |
346 ms |
30716 KB |
Output is correct |
| 3 |
Correct |
352 ms |
30784 KB |
Output is correct |
| 4 |
Incorrect |
360 ms |
37844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
17888 KB |
Output is correct |
| 2 |
Correct |
346 ms |
30716 KB |
Output is correct |
| 3 |
Correct |
352 ms |
30784 KB |
Output is correct |
| 4 |
Incorrect |
360 ms |
37844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
