#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 2e5 + 5;
int n, m, c, p;
int lab[N], cands[N];
long long pf[N];
array<int, 3> pt[N];
array<int, 4> rect[N];
vector<array<int, 3>> edges;
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
bool mrg(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return 0;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
lab[u] += lab[v];
lab[v] = u;
return 1;
}
void bld() {
vector<array<int, 2>> events;
for (int i = 1; i <= m; ++i) {
events.push_back({rect[i][0], rect[i][1]});
events.push_back({rect[i][2] + 1, -rect[i][1]});
}
multiset<int> st;
auto add = [&](int x) {
if (x > 0) {
st.insert(x);
} else if (x < 0) {
st.erase(st.find(-x));
}
};
sort(pt + 1, pt + n + 1);
sort(events.begin(), events.end());
for (int i = 1, j = 0; i <= n; ++i) {
while (j < m && events[j][0] == pt[i][0]) {
add(events[j++][1]);
}
int k = i;
while (k + 1 <= n && pt[k + 1][0] == pt[i][0]) {
++k;
auto it = st.lower_bound(pt[k][1]);
if (it != st.begin() && *prev(it) > pt[k - 1][1]) {
continue;
}
edges.push_back({pt[k][1] - pt[k - 1][1], pt[k][2], pt[k - 1][2]});
}
i = k;
}
}
long long qry(int b, int h) {
if (h + p < n) {
return -1;
}
int cnt = lower_bound(cands + 1, cands + p + 1, b) - cands - 1;
if (cnt + h >= n) {
return pf[cnt] + (long long) (n - cnt) * b;
}
return pf[n - h] + (long long) h * b;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> c;
for (int i = 1; i <= n; ++i) {
int x, y; cin >> x >> y;
pt[i] = {x, y, i};
}
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < 4; ++j) {
cin >> rect[i][j];
}
}
bld();
for (int i = 1; i <= n; ++i) {
swap(pt[i][0], pt[i][1]);
}
for (int i = 1; i <= m; ++i) {
swap(rect[i][0], rect[i][1]);
swap(rect[i][2], rect[i][3]);
}
bld();
fill(lab + 1, lab + n + 1, -1);
for (auto [c, u, v] : edges) {
if (mrg(u, v)) {
cands[++p] = c;
pf[p] = pf[p - 1] + c;
}
}
while (c--) {
int b, h; cin >> b >> h;
cout << qry(b, h) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
