#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
using namespace std;
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
const int N = 6e5 + 7;
int n, m, c, gx, gy, nEdge, cnt, q;
long long revx[N], revy[N];
int p[N];
long long pre[N], Edge[N];
bool InBIT[N];
vector <int> vx, vy;
map <int, int> mpx, mpy;
ii a[N];
struct edge{
int u, v, c;
edge() {}
edge(int u, int v, int c): u(u), v(v), c(c) {}
bool operator < (const edge& b) const{
return c < b.c || (c == b.c && (u < b.u || (u == b.u && (v < b.v))));
}
}e[N];
struct rect{
int p, q, r, s;
}rec[N];
struct Point{
int y, rec, id;
Point() {}
Point(int y, int rec, int id): y(y), rec(rec), id(id) {}
bool operator < (const Point &b) const {
return y < b.y;
}
};
vector <Point> v[N];
struct bit{
int tree[4 * N];
inline void Update(int x, int val){
for (int i = x; i < N; i += (i & (-i)))
tree[i] += val;
}
int Query(int x){
int res = 0;
for (int i = x; i > 0; i -= (i & (-i)))
res += tree[i];
return res;
}
}BIT;
inline void Compress(){
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
mpx[vx[0]] = gx = 1; revx[1] = vx[0];
mpy[vy[0]] = gy = 1; revy[1] = vy[0];
for (int i = 1; i < vx.size(); i++)
if (vx[i] != vx[i - 1]){
mpx[vx[i]] = ++gx;
revx[gx] = vx[i];
}
for (int i = 1; i < vy.size(); i++)
if (vy[i] != vy[i - 1]){
mpy[vy[i]] = ++gy;
revy[gy] = vy[i];
}
for (int i = 1; i <= n; i++){
a[i].x = mpx[a[i].x]; a[i].y = mpy[a[i].y];
}
for (int i = 1; i <= m; i++){
rec[i].p = mpx[rec[i].p]; rec[i].q = mpy[rec[i].q];
rec[i].r = mpx[rec[i].r]; rec[i].s = mpy[rec[i].s];
}
}
inline void Flip(){
for (int i = 1; i <= n; i++)
swap(a[i].x, a[i].y);
for (int i = 1; i <= m; i++){
swap(rec[i].p, rec[i].q);
swap(rec[i].r, rec[i].s);
}
swap(gx, gy);
}
inline void Update(Point x){
if (!x.rec)
return;
if (x.id == 1)
BIT.Update(x.y, 1);
else
BIT.Update(x.y, -1);
}
inline void AddEdge(int u, int v, long long revy[]){
e[++nEdge] = edge(u, v, abs(revy[a[u].y] - revy[a[v].y]));
}
inline void SweepLine(long long revy[]){
for (int i = 1; i <= gx; i++)
v[i].clear();
for (int i = 1; i <= n; i++){
v[a[i].x].push_back(Point(a[i].y, 0, i));
}
for (int i = 1; i <= m; i++){
v[rec[i].p].push_back(Point(rec[i].q, 1, 1));
v[rec[i].r].push_back(Point(rec[i].s, 1, -1));
v[rec[i].p].push_back(Point(rec[i].s, 1, 1));
v[rec[i].r].push_back(Point(rec[i].q, 1, -1));
}
for (int i = 1; i <= gx; i++)
sort(v[i].begin(), v[i].end());
for (int i = 1; i <= gx; i++)
if (v[i].size()){
Update(v[i][0]);
for (int j = 1; j < v[i].size(); j++){
Update(v[i][j]);
if (!v[i][j].rec && !v[i][j - 1].rec)
if (BIT.Query(v[i][j].y) == BIT.Query(v[i][j - 1].y))
AddEdge(v[i][j].id, v[i][j - 1].id, revy);
}
}
}
int Find(int u){
if (p[u] < 0) return u;
return p[u] = Find(p[u]);
}
inline void Union(int u, int v){
int x = p[u] + p[v];
if (p[u] < p[v]){
p[v] = u;
p[u] = x;
}
else{
p[u] = v;
p[v] = x;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
read(n); read(m); read(q);
for (int i = 1; i <= n; i++){
read(a[i].x); read(a[i].y);
vx.push_back(a[i].x);
vy.push_back(a[i].y);
}
for (int i = 1; i <= m; i++){
read(rec[i].p); read(rec[i].q); read(rec[i].r); read(rec[i].s);
vx.push_back(rec[i].p); vx.push_back(rec[i].r);
vy.push_back(rec[i].q); vy.push_back(rec[i].s);
}
Compress();
SweepLine(revy); Flip();
SweepLine(revx); Flip();
memset(p, -1, sizeof(p));
sort(e + 1, e + nEdge + 1);
int CC = n;
for (int i = 1; i <= nEdge; i++){
int u = Find(e[i].u);
int v = Find(e[i].v);
int c = e[i].c;
if (u != v){
Union(u, v);
Edge[++cnt] = c;
CC--;
if (cnt == n - 1)
break;
}
}
for (int i = 1; i <= cnt; i++)
pre[i] = pre[i - 1] + Edge[i];
int Cost, Num;
for (int i = 1; i <= q; i++){
read(Cost); read(Num);
if (Num < CC){
writeln(-1);
continue;
}
int l = 1;
int r = cnt;
while (l <= r){
int mid = (l + r) / 2;
if (Edge[mid] <= Cost)
l = mid + 1;
else
r = mid - 1;
}
int pos = l;
int Add = min(Num - CC, cnt - pos + 1);
writeln(pre[max(0, cnt - Add)] + 1LL * (Add + CC) * Cost);
}
}
Compilation message
construction.cpp: In function 'void Compress()':
construction.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < vx.size(); i++)
^
construction.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < vy.size(); i++)
^
construction.cpp: In function 'void SweepLine(long long int*)':
construction.cpp:129:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < v[i].size(); j++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
70176 KB |
Output is correct |
| 2 |
Correct |
633 ms |
86200 KB |
Output is correct |
| 3 |
Correct |
603 ms |
85804 KB |
Output is correct |
| 4 |
Correct |
243 ms |
74980 KB |
Output is correct |
| 5 |
Correct |
563 ms |
85804 KB |
Output is correct |
| 6 |
Correct |
599 ms |
85804 KB |
Output is correct |
| 7 |
Correct |
149 ms |
73668 KB |
Output is correct |
| 8 |
Correct |
449 ms |
91520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2963 ms |
142108 KB |
Output is correct |
| 2 |
Correct |
2879 ms |
142108 KB |
Output is correct |
| 3 |
Correct |
2923 ms |
142240 KB |
Output is correct |
| 4 |
Correct |
2923 ms |
142240 KB |
Output is correct |
| 5 |
Correct |
683 ms |
93796 KB |
Output is correct |
| 6 |
Correct |
656 ms |
85804 KB |
Output is correct |
| 7 |
Correct |
3249 ms |
142108 KB |
Output is correct |
| 8 |
Correct |
403 ms |
102296 KB |
Output is correct |
| 9 |
Correct |
386 ms |
101604 KB |
Output is correct |
| 10 |
Correct |
1503 ms |
144004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
913 ms |
85804 KB |
Output is correct |
| 2 |
Correct |
859 ms |
85808 KB |
Output is correct |
| 3 |
Correct |
809 ms |
86200 KB |
Output is correct |
| 4 |
Correct |
386 ms |
75376 KB |
Output is correct |
| 5 |
Correct |
826 ms |
90160 KB |
Output is correct |
| 6 |
Correct |
1036 ms |
87916 KB |
Output is correct |
| 7 |
Correct |
963 ms |
85804 KB |
Output is correct |
| 8 |
Correct |
903 ms |
85804 KB |
Output is correct |
| 9 |
Correct |
339 ms |
73536 KB |
Output is correct |
| 10 |
Correct |
743 ms |
91520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3283 ms |
142108 KB |
Output is correct |
| 2 |
Correct |
1679 ms |
112932 KB |
Output is correct |
| 3 |
Correct |
2796 ms |
142108 KB |
Output is correct |
| 4 |
Correct |
709 ms |
86992 KB |
Output is correct |
| 5 |
Correct |
3143 ms |
142112 KB |
Output is correct |
| 6 |
Correct |
829 ms |
88708 KB |
Output is correct |
| 7 |
Correct |
3289 ms |
151612 KB |
Output is correct |
| 8 |
Correct |
3126 ms |
142112 KB |
Output is correct |
| 9 |
Correct |
599 ms |
101024 KB |
Output is correct |
| 10 |
Correct |
1733 ms |
144004 KB |
Output is correct |
| 11 |
Correct |
786 ms |
93068 KB |
Output is correct |
