#include <bits/stdc++.h>
#define llint long long
#define fi first
#define se second
using namespace std;
inline void read(int &x) {
register char c = getchar();
while (c < '0' || c > '9') c = getchar();
x = 0;
while ('0' <= c && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
}
int cs[20], ncs;
inline void writeln(llint x) {
if (x == -1) {
puts("-1");
return;
}
ncs = 0;
while (x) {
cs[++ncs] = x % 10;
x /= 10;
}
for (int i = ncs; i >= 1; --i) {
putchar(cs[i] + '0');
}
putchar('\n');
}
void openFile() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
#ifdef Tr___
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#else
//freopen("name.inp", "r", stdin);
//freopen("name.out", "w", stdout);
#endif
}
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
const llint inf = 1e9 + 7;
int N, M, C;
struct point {
int x, y;
int id;
} p[maxn * 2];
struct rect {
int x, y, u, v;
rect() {}
rect(int x, int y, int u, int v): x(x), y(y), u(u), v(v) {}
} rec[maxn * 2], realRec[maxn * 4];
struct query {
int b, h;
} q[maxn * 5];
void enter() {
read(N); read(M); read(C);
for (int i = 1; i <= N; ++i) {
read(p[i].x); read(p[i].y);
//cin >> p[i].x >> p[i].y;
p[i].id = i;
}
for (int i = 1; i <= M; ++i) {
read(rec[i].x); read(rec[i].y); read(rec[i].u); read(rec[i].v);
//cin >> rec[i].x >> rec[i].y >> rec[i].u >> rec[i].v;
}
for (int i = 1; i <= C; ++i) {
read(q[i].b); read(q[i].h);
//cin >> q[i].b >> q[i].h;
//h <= 1e5
}
}
int lastId;
multiset<int> coor;
bool checkCoor(int x, int u, int v) {
while (lastId <= M * 2 && realRec[lastId].x <= x) {
if (realRec[lastId].v == 1) {
coor.insert(realRec[lastId].y);
coor.insert(realRec[lastId].u);
}
else {
coor.erase(coor.find(realRec[lastId].y));
coor.erase(coor.find(realRec[lastId].u));
}
++lastId;
}
multiset<int> :: iterator it = coor.lower_bound(u);
if (it == coor.end()) return true;
if (*it <= v) return false;
return true;
}
struct edge {
int u, v, w;
edge() {}
edge(int u, int v, int w): u(u), v(v), w(w) {}
};
vector<edge> E;
inline void addEdge(int u, int v, int w) {
E.push_back(edge(u, v, w));
//cout << u << " " << v << " " << w << endl;
}
bool sortByX(const point &a, const point &b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool sortByY(const point &a, const point &b) {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
void buildEdge() {
//num edge
sort(p + 1, p + N + 1, sortByX);
for (int i = 1; i <= M; ++i) {
realRec[i] = rect(rec[i].x, rec[i].y, rec[i].v, 1);
realRec[i + M] = rect(rec[i].u + 1, rec[i].y, rec[i].v, -1);
}
sort(realRec + 1, realRec + M * 2 + 1, [] (const rect &a, const rect &b) {
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
if (a.u != b.u) return a.u < b.u;
return a.v > b.v;
});
coor.clear();
lastId = 1;
for (int i = 2; i <= N; ++i) {
if (p[i].x != p[i - 1].x) continue;
if (checkCoor(p[i].x, p[i - 1].y, p[i].y)) {
addEdge(p[i - 1].id, p[i].id, p[i].y - p[i - 1].y);
}
}
sort(p + 1, p + N + 1, sortByY);
for (int i = 1; i <= M; ++i) {
realRec[i] = rect(rec[i].y, rec[i].x, rec[i].u, 1);
realRec[i + M] = rect(rec[i].v, rec[i].x, rec[i].u, -1);
}
sort(realRec + 1, realRec + M * 2 + 1, [] (const rect &a, const rect &b) {
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
if (a.u != b.u) return a.u < b.u;
return a.v > b.v;
});
coor.clear();
lastId = 1;
for (int i = 2; i <= N; ++i) {
if (p[i].y != p[i - 1].y) continue;
//cout << p[i - 1].id << " " << p[i].id << endl;
if (checkCoor(p[i].y, p[i - 1].x, p[i].x)) {
addEdge(p[i - 1].id, p[i].id, p[i].x - p[i - 1].x);
}
}
}
int lab[maxn * 2];
int find(int u) {
return lab[u] <= 0 ? u : u = find(lab[u]);
}
inline void Union(int s, int t) {
if (lab[s] < lab[t]) lab[t] = s;
else {
if (lab[s] == lab[t]) --lab[t];
lab[s] = t;
}
}
vector<int> allEdge;
void buildMST() {
sort(E.begin(), E.end(), [] (const edge &a, const edge &b) {
return a.w < b.w;
});
for (auto e : E) {
int s = e.u, t = e.v, w = e.w;
s = find(s), t = find(t);
if (s != t) {
Union(s, t);
allEdge.push_back(w);
//cout << e.u << " " << e.v << " " << e.w << endl;
}
}
}
void calcQuery() {
//allEdge already sorted
vector<llint> tot;
tot.clear();
for (int i = 0; i < allEdge.size(); ++i) {
if (i == 0) tot.push_back(allEdge[i]);
else tot.push_back(tot[i - 1] + allEdge[i]);
//cout << allEdge[i] << endl;
}
if (tot.empty()) tot.push_back(0);
int tplt = N - allEdge.size();
for (int i = 1; i <= C; ++i) {
if (tplt <= q[i].h) {
llint res = 1ll * tplt * q[i].b;
// cout << "r: " << res << endl;
//q[i].h - tplt
int mx = upper_bound(allEdge.begin(), allEdge.end(), q[i].b) - allEdge.begin();
if (mx == allEdge.size()) {
writeln(res + tot.back());
continue;
}
//mx: id > q[i].b
int sl = allEdge.size() - mx;
sl = min(sl, q[i].h - tplt);
mx = allEdge.size() - sl - 1;
// cout << mx << endl;
// cout << "r: " << tot[mx] << endl;
res = res + 1ll * q[i].b * sl + (mx >= 0 ? tot[mx] : 0);
writeln(res);
}
else {
writeln(-1);
}
}
}
void solve() {
buildEdge();
buildMST();
calcQuery();
}
int main() {
openFile();
enter();
solve();
return 0;
}
Compilation message
construction.cpp: In function 'void calcQuery()':
construction.cpp:208:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < allEdge.size(); ++i) {
^
construction.cpp:221:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (mx == allEdge.size()) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
18600 KB |
Output is correct |
| 2 |
Correct |
119 ms |
22996 KB |
Output is correct |
| 3 |
Correct |
126 ms |
22996 KB |
Output is correct |
| 4 |
Incorrect |
129 ms |
29904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
759 ms |
20184 KB |
Output is correct |
| 2 |
Correct |
753 ms |
20184 KB |
Output is correct |
| 3 |
Correct |
846 ms |
20184 KB |
Output is correct |
| 4 |
Correct |
816 ms |
20184 KB |
Output is correct |
| 5 |
Incorrect |
546 ms |
19732 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
393 ms |
22996 KB |
Output is correct |
| 2 |
Correct |
373 ms |
26836 KB |
Output is correct |
| 3 |
Correct |
313 ms |
22996 KB |
Output is correct |
| 4 |
Incorrect |
299 ms |
29904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1096 ms |
20184 KB |
Output is correct |
| 2 |
Correct |
526 ms |
19392 KB |
Output is correct |
| 3 |
Correct |
876 ms |
20188 KB |
Output is correct |
| 4 |
Correct |
229 ms |
19024 KB |
Output is correct |
| 5 |
Correct |
863 ms |
20188 KB |
Output is correct |
| 6 |
Correct |
273 ms |
18748 KB |
Output is correct |
| 7 |
Correct |
739 ms |
19788 KB |
Output is correct |
| 8 |
Correct |
949 ms |
20184 KB |
Output is correct |
| 9 |
Correct |
659 ms |
29904 KB |
Output is correct |
| 10 |
Correct |
643 ms |
41492 KB |
Output is correct |
| 11 |
Correct |
456 ms |
27772 KB |
Output is correct |
