#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXM = 2e5;
const int MAXC = 5e5;
const int MAXV = 2e6;
const ll INF = 1e18;
struct Point
{
int x, y, p;
};
struct Rect
{
int x1, y1, x2, y2;
};
struct Line
{
int x, y1, y2, p, q;
};
struct Edge
{
int u, v, w;
};
struct Query
{
ll B, H;
};
int N, M, C;
Point A[MAXN+10];
Rect B[MAXM+10];
Query D[MAXC+10];
vector<int> comp;
vector<Edge> E;
void massert(bool p)
{
if(!p) while(1);
}
int getcomp(int x)
{
return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
}
ll tree[MAXV*4+10], lazy[MAXV*4+10];
void init()
{
memset(tree, 0, sizeof(tree));
memset(lazy, 0, sizeof(lazy));
}
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
tree[node]+=lazy[node]*(tr-tl+1);
if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r, int k)
{
massert(1<=l && l<=MAXV);
massert(1<=r && r<=MAXV);
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=tree[node*2]+tree[node*2+1];
}
ll query(int node, int tl, int tr, int l, int r)
{
massert(1<=l && l<=MAXV);
massert(1<=r && r<=MAXV);
busy(node, tl, tr);
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
}
int par[MAXN+10];
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
par[x]=y;
}
ll VV[MAXN+10];
int main()
{
scanf("%d%d%d", &N, &M, &C);
for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
for(int i=1; i<=M; i++) scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
for(int i=1; i<=N; i++) comp.push_back(A[i].x), comp.push_back(A[i].y);
for(int i=1; i<=M; i++) comp.push_back(B[i].x1), comp.push_back(B[i].x2), comp.push_back(B[i].y1), comp.push_back(B[i].y2);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
massert(comp.size()<=MAXV);
{
vector<Line> V; init();
sort(A+1, A+N+1, [&](const Point &p, const Point &q)
{
if(p.x==q.x) return p.y<q.y;
return p.x<q.x;
});
for(int i=2; i<=N; i++)
{
if(A[i].x!=A[i-1].x) continue;
V.push_back({A[i].x, A[i-1].y, A[i].y, 0, i});
}
for(int i=1; i<=M; i++)
{
V.push_back({B[i].x1, B[i].y1, B[i].y2, 1, 0});
V.push_back({B[i].x2, B[i].y1, B[i].y2, -1, 0});
}
sort(V.begin(), V.end(), [&](const Line &p, const Line &q)
{
if(p.x!=q.x) return p.x<q.x;
return p.p>q.p;
});
for(auto it : V)
{
if(it.p!=0)
{
update(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2), it.p);
}
else
{
massert(query(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y1))==0);
massert(query(1, 1, comp.size(), getcomp(it.y2), getcomp(it.y2))==0);
if(query(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2))==0)
{
E.push_back({A[it.q-1].p, A[it.q].p, A[it.q].y-A[it.q-1].y});
}
}
}
}
//for(auto it : E) printf("E : %d %d %d\n", it.u, it.v, it.w);
{
vector<Line> V; init();
sort(A+1, A+N+1, [&](const Point &p, const Point &q)
{
if(p.y==q.y) return p.x<q.x;
return p.y<q.y;
});
for(int i=2; i<=N; i++)
{
if(A[i].y!=A[i-1].y) continue;
V.push_back({A[i].y, A[i-1].x, A[i].x, 0, i});
}
for(int i=1; i<=M; i++)
{
V.push_back({B[i].y1, B[i].x1, B[i].x2, 1, 0});
V.push_back({B[i].y2, B[i].x1, B[i].x2, -1, 0});
}
sort(V.begin(), V.end(), [&](const Line &p, const Line &q)
{
if(p.x!=q.x) return p.x<q.x;
return p.p>q.p;
});
for(auto it : V)
{
if(it.p!=0)
{
update(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2), it.p);
}
else
{
massert(query(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y1))==0);
massert(query(1, 1, comp.size(), getcomp(it.y2), getcomp(it.y2))==0);
if(query(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2))==0)
{
E.push_back({A[it.q-1].p, A[it.q].p, A[it.q].x-A[it.q-1].x});
}
}
}
}
//for(auto it : E) printf("E : %d %d %d\n", it.u, it.v, it.w);
for(int i=1; i<=N; i++) par[i]=i;
sort(E.begin(), E.end(), [&](const Edge &p, const Edge &q)
{
return p.w<q.w;
});
int S=0;
for(auto it : E)
{
if(Find(it.u)==Find(it.v)) continue;
Union(it.u, it.v);
S++;
VV[S]=VV[S-1]+it.w;
massert(it.w>0);
}
massert(S<N);
for(int i=1; i<=C; i++)
{
scanf("%lld%lld", &D[i].B, &D[i].H);
if(N-D[i].H>S) { return printf("-1\n"); printf("\n"); }
ll ans=INF;
for(int j=N-D[i].H; j<=S; j++)
{
ans=min(ans, (N-j)*D[i].B+VV[j]);
}
if(ans==INF) ans=-1;
printf("%lld\n", ans);
}
return 0;
}
Compilation message
construction.cpp: In function 'void update(int, int, int, int, int, int)':
construction.cpp:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid=tl+tr>>1;
| ~~^~~
construction.cpp: In function 'll query(int, int, int, int, int)':
construction.cpp:100:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
100 | int mid=tl+tr>>1;
| ~~^~~
construction.cpp: In function 'int main()':
construction.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | scanf("%d%d%d", &N, &M, &C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:122:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:123:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | for(int i=1; i<=M; i++) scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:239:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
239 | scanf("%lld%lld", &D[i].B, &D[i].H);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
126440 KB |
Output is correct |
| 2 |
Runtime error |
637 ms |
136468 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
126440 KB |
Output is correct |
| 2 |
Runtime error |
637 ms |
136468 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
126440 KB |
Output is correct |
| 2 |
Runtime error |
637 ms |
136468 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
126440 KB |
Output is correct |
| 2 |
Runtime error |
637 ms |
136468 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
