#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6e5;
const ll INF = 2e18;
struct Point { int x, y, p; };
struct Rect { int x1, y1, x2, y2; };
struct Line
{
int x, y1, y2, p;
bool operator < (const Line &p) const { return x<p.x; }
};
struct Edge
{
int u, v, w;
bool operator < (const Edge &p) const { return w<p.w; }
};
int N, M, C, SX, SY, S;
Point A[MAXN+10];
Rect B[MAXN+10];
vector<int> xcomp, ycomp;
vector<Edge> E;
ll D[MAXN+10];
int getxcomp(int x) { return lower_bound(xcomp.begin(), xcomp.end(), x)-xcomp.begin()+1; }
int getycomp(int y) { return lower_bound(ycomp.begin(), ycomp.end(), y)-ycomp.begin()+1; }
struct BIT
{
int tree[MAXN+10];
BIT() { memset(tree, 0, sizeof(tree)); }
void update(int i, int v) { for(; i<=S; i+=(i&-i)) tree[i]+=v; }
void updater(int l, int r) { update(l, 1); update(r+1, -1); }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;
int xcnt[MAXN+10], ycnt[MAXN+10];
int par[MAXN+10];
int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; }
struct CLine { ll a, b; };
double cross(const CLine &p, const CLine &q) { return (double)(q.b-p.b)/(p.a-q.a); }
struct CHT
{
vector<CLine> S;
void update(CLine p)
{
while(S.size()>1 && cross(S[S.size()-1], p)>=cross(S[S.size()-1], S[S.size()-2])) S.pop_back();
S.push_back(p);
}
ll query(ll x)
{
int lo=0, hi=S.size();
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(mid==0 || cross(S[mid], S[mid-1])>=x) lo=mid;
else hi=mid;
}
return S[lo].a*x+S[lo].b;
}
} cht;
struct Query
{
ll b; int h, p;
bool operator < (const Query &p) const { return h<p.b; }
}query[MAXN+10];
ll ans[MAXN+10];
int main()
{
int i, j;
scanf("%d%d%d", &N, &M, &C);
for(i=1; i<=N; i++)
{
scanf("%d%d", &A[i].x, &A[i].y); A[i].p=i;
xcomp.push_back(A[i].x);
ycomp.push_back(A[i].y);
}
for(i=1; i<=M; i++)
{
scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
xcomp.push_back(B[i].x1); xcomp.push_back(B[i].x2);
ycomp.push_back(B[i].y1); ycomp.push_back(B[i].y2);
}
for(i=1; i<=C; i++) scanf("%lld%d", &query[i].b, &query[i].h), query[i].p=i;
return 0;
sort(query+1, query+C+1);
sort(xcomp.begin(), xcomp.end());
xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
sort(ycomp.begin(), ycomp.end());
ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
SX=xcomp.size(); SY=ycomp.size(); S=max(SX, SY);
vector<Line> todo;
todo.clear(); bit=BIT();
for(i=1; i<=M; i++) todo.push_back({B[i].x1, B[i].y1, B[i].y2, 0}), todo.push_back({B[i].x2, B[i].y1, B[i].y2, 0});
for(i=1; i<=N; i++) todo.push_back({A[i].x, A[i].y, A[i].y, A[i].p});
sort(todo.begin(), todo.end());
for(auto it : todo)
{
if(it.p==0) bit.updater(getycomp(it.y1), getycomp(it.y2));
else xcnt[it.p]=bit.query(getycomp(it.y1));
}
todo.clear(); bit=BIT();
for(i=1; i<=M; i++) todo.push_back({B[i].y1, B[i].x1, B[i].x2, 0}), todo.push_back({B[i].y2, B[i].x1, B[i].x2, 0});
for(i=1; i<=N; i++) todo.push_back({A[i].y, A[i].x, A[i].x, A[i].p});
sort(todo.begin(), todo.end());
for(auto it : todo)
{
if(it.p==0) bit.updater(getxcomp(it.y1), getxcomp(it.y2));
else ycnt[it.p]=bit.query(getxcomp(it.y1));
}
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(i=1; i<=N;)
{
int y=A[i].y;
for(i++; i<=N && A[i].y==y; i++)
{
if(xcnt[A[i].p]==xcnt[A[i-1].p])
{
int u=A[i].p, v=A[i-1].p, w=A[i].x-A[i-1].x;
E.push_back({u, v, w});
}
}
}
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(i=1; i<=N;)
{
int x=A[i].x;
for(i++; i<=N && A[i].x==x; i++)
{
if(ycnt[A[i].p]==ycnt[A[i-1].p])
{
int u=A[i].p, v=A[i-1].p, w=A[i].y-A[i-1].y;
E.push_back({u, v, w});
}
}
}
sort(E.begin(), E.end());
for(i=1; i<=N; i++) par[i]=i;
for(i=1; i<N; i++) D[i]=INF;
int cnt=N;
for(auto it : E)
{
if(Find(it.u)==Find(it.v)) continue;
Union(it.u, it.v);
cnt--; D[cnt]=D[cnt+1]+it.w;
}
for(i=1, j=1; i<=C; i++)
{
for(; j<=query[i].h; j++) cht.update({j, D[j]});
ans[query[i].p]=cht.query(query[i].b);
if(ans[query[i].p]>=INF) ans[query[i].p]=-1;
}
for(i=1; i<=C; i++) printf("%lld\n", ans[i]);
}
Compilation message
construction.cpp: In member function 'll CHT::query(ll)':
construction.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
construction.cpp: In function 'int main()':
construction.cpp:83:7: 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:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i].x, &A[i].y); A[i].p=i;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:96:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=C; i++) scanf("%lld%d", &query[i].b, &query[i].h), query[i].p=i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
3064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
217 ms |
14024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
14692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
352 ms |
20940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
