#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lf;
typedef pair<int, int> pii;
const int MN = 600010;
int N, M, C;
pii P[MN];
struct Rect {
int x1, y1, x2, y2;
};
Rect rect[MN];
struct Query {
int b, h, id;
bool operator <(const Query &i) const {
return h < i.h;
}
};
Query Q[MN];
int Xn, Yn;
vector<int> X, Y;
unordered_map<int, int> dx, dy;
struct BIT {
vector<int> tree, lazy;
void init() {
tree = vector<int>(4 * MN, 0);
lazy = vector<int>(4 * MN, 0);
}
void prop(int l, int r, int n) {
if(l != r) {
tree[2*n] += lazy[n];
lazy[2*n] += lazy[n];
tree[2*n + 1] += lazy[n];
lazy[2*n + 1] += lazy[n];
lazy[n] = 0;
}
}
void upd(int a, int b, int d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n] += d;
lazy[n] += d;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd(a, b, d, l, m, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
prop(l, r, n);
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return max(L, R);
}
} bit;
struct Edge {
int u, v, w;
bool operator <(const Edge &i) const {
return w < i.w;
}
};
vector<Edge> edge;
vector<pii> query[MN], add[MN], rem[MN];
void proc(vector<int> &Z) {
for(int i = 0; i < MN; i++) {
query[i].clear();
add[i].clear();
rem[i].clear();
}
for(int i = 0; i < N; i++) {
query[ P[i].second ].push_back({ P[i].first, i });
}
for(int i = 0; i < M; i++) {
add[ rect[i].y1 ].push_back({ rect[i].x1, rect[i].x2 });
rem[ rect[i].y2 ].push_back({ rect[i].x1, rect[i].x2 });
}
bit.init();
for(int i = 0; i < MN; i++) {
for(int j = 0; j < add[i].size(); j++) {
bit.upd(add[i][j].first, add[i][j].second, 1, 0, MN - 1, 1);
}
sort(query[i].begin(), query[i].end());
for(int j = 1; j < query[i].size(); j++) {
int x1 = query[i][j - 1].first;
int x2 = query[i][j].first;
if(!bit.quer(x1, x2, 0, MN - 1, 1)) {
int id1 = query[i][j - 1].second;
int id2 = query[i][j].second;
edge.push_back({ id1, id2, Z[x2] - Z[x1] });
}
}
for(int j = 0; j < rem[i].size(); j++) {
bit.upd(rem[i][j].first, rem[i][j].second, -1, 0, MN - 1, 1);
}
}
}
struct CHT {
vector<ll> M, B;
void init() {
M.clear();
B.clear();
}
bool bad(int l1, int l2, int l3) {
return (lf) (B[l3] - B[l1]) / (M[l1] - M[l3]) <= (lf) (B[l2] - B[l1]) / (M[l1] - M[l2]);
}
void add(ll m, ll b) {
M.push_back(m);
B.push_back(b);
while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
M.erase(M.end() - 2);
B.erase(B.end() - 2);
}
if(M.size() == 2 && M[0] == M[1]) {
M.erase(M.end() - 2);
B.erase(B.end() - 2);
}
}
ll query(ll x) {
if(M.size() == 0) return 1e18;
int s = 0, e = (int)M.size() - 2, p = 0;
while(s <= e) {
int m = (s + e)>>1;
if(x >= (lf) (B[m + 1] - B[m]) / (M[m] - M[m + 1])) {
p = m + 1;
s = m + 1;
}
else e = m - 1;
}
return M[p] * x + B[p];
}
} cht;
int fa[MN];
void init() {
for(int i = 0; i < N; i++) fa[i] = i;
}
int find(int u) {
if(fa[u] == u) return u;
else return fa[u] = find(fa[u]);
}
void mrg(int u, int v) {
u = find(u);
v = find(v);
fa[v] = u;
}
vector<pair<int, ll> > line;
ll ans[MN];
int main() {
scanf("%d %d %d", &N, &M, &C);
for(int i = 0; i < N; i++) {
scanf("%d %d", &P[i].first, &P[i].second);
X.push_back(P[i].first);
Y.push_back(P[i].second);
}
for(int i = 0; i < M; i++) {
int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
rect[i] = {x1, y1, x2, y2};
X.push_back(x1);
X.push_back(x2);
Y.push_back(y1);
Y.push_back(y2);
}
for(int i = 0; i < C; i++) {
scanf("%d %d", &Q[i].b, &Q[i].h);
Q[i].id = i;
}
sort(Q, Q + C);
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
X.resize(unique(X.begin(), X.end()) - X.begin());
Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
Xn = X.size();
Yn = Y.size();
for(int i = 0; i < Xn; i++) dx[X[i]] = i;
for(int i = 0; i < Yn; i++) dy[Y[i]] = i;
for(int i = 0; i < N; i++) {
P[i].first = dx[ P[i].first ];
P[i].second = dy[ P[i].second ];
}
for(int i = 0; i < M; i++) {
rect[i].x1 = dx[ rect[i].x1 ];
rect[i].x2 = dx[ rect[i].x2 ];
rect[i].y1 = dy[ rect[i].y1 ];
rect[i].y2 = dy[ rect[i].y2 ];
}
proc(X);
for(int i = 0; i < N; i++) swap(P[i].first, P[i].second);
for(int i = 0; i < M; i++) {
swap(rect[i].x1, rect[i].y1);
swap(rect[i].x2, rect[i].y2);
}
proc(Y);
sort(edge.begin(), edge.end());
init();
int cnt = N;
ll cost = 0;
line.push_back({cnt, cost});
for(int i = 0; i < edge.size(); i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
if(find(u) == find(v)) continue;
mrg(u, v);
cnt--;
cost += w;
line.push_back({cnt, cost});
}
/*
for(int i = 0; i < line.size(); i++) {
cout << line[i].first << ' ' << line[i].second << endl;
}
//*/
cht.init();
int pos = (int)line.size() - 1;
for(int i = 0; i < C; i++) {
while(pos >= 0 && line[pos].first <= Q[i].h) {
cht.add(-line[pos].first, line[pos].second);
pos--;
}
ans[ Q[i].id ] = cht.query(-Q[i].b);
}
for(int i = 0; i < C; i++) {
if(ans[i] == 1e18) printf("-1\n");
else printf("%lld\n", ans[i]);
}
}
Compilation message
construction.cpp: In function 'void proc(std::vector<int>&)':
construction.cpp:93:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < add[i].size(); j++) {
~~^~~~~~~~~~~~~~~
construction.cpp:99:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1; j < query[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
construction.cpp:111:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < rem[i].size(); j++) {
~~^~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:227:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < edge.size(); i++) {
~~^~~~~~~~~~~~~
construction.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &M, &C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &P[i].first, &P[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:179:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &Q[i].b, &Q[i].h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
151 ms |
73156 KB |
Output is correct |
| 2 |
Correct |
690 ms |
88684 KB |
Output is correct |
| 3 |
Correct |
755 ms |
88684 KB |
Output is correct |
| 4 |
Correct |
472 ms |
88684 KB |
Output is correct |
| 5 |
Correct |
557 ms |
90296 KB |
Output is correct |
| 6 |
Correct |
689 ms |
90296 KB |
Output is correct |
| 7 |
Correct |
349 ms |
90296 KB |
Output is correct |
| 8 |
Correct |
548 ms |
93024 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3011 ms |
155752 KB |
Output is correct |
| 2 |
Correct |
3203 ms |
155800 KB |
Output is correct |
| 3 |
Correct |
3029 ms |
159952 KB |
Output is correct |
| 4 |
Correct |
3136 ms |
160020 KB |
Output is correct |
| 5 |
Correct |
879 ms |
160020 KB |
Output is correct |
| 6 |
Correct |
551 ms |
160020 KB |
Output is correct |
| 7 |
Correct |
3220 ms |
160032 KB |
Output is correct |
| 8 |
Correct |
769 ms |
160032 KB |
Output is correct |
| 9 |
Correct |
833 ms |
160032 KB |
Output is correct |
| 10 |
Correct |
1897 ms |
160032 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1093 ms |
160032 KB |
Output is correct |
| 2 |
Correct |
1234 ms |
160032 KB |
Output is correct |
| 3 |
Correct |
868 ms |
160032 KB |
Output is correct |
| 4 |
Correct |
694 ms |
160032 KB |
Output is correct |
| 5 |
Correct |
919 ms |
160032 KB |
Output is correct |
| 6 |
Correct |
1108 ms |
160032 KB |
Output is correct |
| 7 |
Correct |
1149 ms |
160032 KB |
Output is correct |
| 8 |
Correct |
1076 ms |
160032 KB |
Output is correct |
| 9 |
Correct |
765 ms |
160032 KB |
Output is correct |
| 10 |
Correct |
1149 ms |
160032 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3562 ms |
168776 KB |
Output is correct |
| 2 |
Correct |
1908 ms |
168776 KB |
Output is correct |
| 3 |
Correct |
3453 ms |
168776 KB |
Output is correct |
| 4 |
Correct |
978 ms |
168776 KB |
Output is correct |
| 5 |
Correct |
2981 ms |
168776 KB |
Output is correct |
| 6 |
Correct |
865 ms |
168776 KB |
Output is correct |
| 7 |
Correct |
3025 ms |
208320 KB |
Output is correct |
| 8 |
Correct |
2857 ms |
218472 KB |
Output is correct |
| 9 |
Correct |
1041 ms |
218472 KB |
Output is correct |
| 10 |
Correct |
2124 ms |
226980 KB |
Output is correct |
| 11 |
Correct |
1022 ms |
226980 KB |
Output is correct |
