#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const ll MAX=1<<18;
const ll INFLL=0x3f3f3f3f3f3f3f;
struct vill{
ll x,y,idx;
};
vill v[MAX];
struct edge{
ll x,y,d;
bool operator<(const edge &a)const{
return d<a.d;
}
};
struct area{ll x1,y1,x2,y2;};
area h[MAX];
vector<ll> ixcp,iycp,ex[2*MAX],ey[2*MAX],val,val2;
vector<edge> mst;
vector<pll> conn[MAX];
multiset<ll> pos;
ll chk[MAX],n,m,c,par[MAX],cum;
ll x_getidx(ll x){return lower_bound(ixcp.begin(),ixcp.end(),x)-ixcp.begin();}
ll y_getidx(ll y){return lower_bound(iycp.begin(),iycp.end(),y)-iycp.begin();}
ll fnd(ll x){
if(par[x]==x) return x;
return par[x]=fnd(par[x]);
}
void uni(ll x,ll y){
x=fnd(x), y=fnd(y);
if(x==y) return;
par[x]=y;
}
bool cmpx(vill a,vill b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
bool cmpy(vill a,vill b){
if(a.y!=b.y) return a.y<b.y;
return a.x<b.x;
}
ll exist(ll x,ll y){
set<ll>::iterator it=pos.lower_bound(x);
if(it==pos.end()) return false;
if(*it<=y) return true;
return false;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&c);
for(ll i=0;i<n;i++){scanf("%lld%lld",&v[i].x,&v[i].y),v[i].idx=i;}
for(ll i=0;i<m;i++){scanf("%lld%lld%lld%lld",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;}
for(ll i=0;i<m;i++) {
ixcp.push_back(h[i].x1); ixcp.push_back(h[i].x2);
iycp.push_back(h[i].y1), iycp.push_back(h[i].y2);
}
sort(ixcp.begin(),ixcp.end());
sort(iycp.begin(),iycp.end());
ixcp.erase(unique(ixcp.begin(),ixcp.end()),ixcp.end());
iycp.erase(unique(iycp.begin(),iycp.end()),iycp.end());
for(ll i=0;i<m;i++){
ex[x_getidx(h[i].x1)].push_back(i), ey[y_getidx(h[i].y1)].push_back(i);
ex[x_getidx(h[i].x2)].push_back(i), ey[y_getidx(h[i].y2)].push_back(i);
}
pos.clear();
sort(v,v+n,cmpx);
for(ll i=1,pt=0;i<n;i++){
if(v[i-1].x==v[i].x){
for(;pt<ixcp.size();pt++){
if(ixcp[pt]>v[i].x) break;
for(ll j=0;j<ex[pt].size();j++) {
if(chk[ex[pt][j]]) pos.erase(pos.lower_bound(h[ex[pt][j]].y1)),pos.erase(pos.lower_bound(h[ex[pt][j]].y2-1));
else pos.insert(h[ex[pt][j]].y1),pos.insert(h[ex[pt][j]].y2-1);
chk[ex[pt][j]]=!chk[ex[pt][j]];
}
}
if(!exist(v[i-1].y,v[i].y)){
ll dist=v[i].y-v[i-1].y;
conn[v[i].idx].push_back(make_pair(v[i-1].idx,dist));
conn[v[i-1].idx].push_back(make_pair(v[i].idx,dist));
}
}
}
pos.clear();
for(ll i=0;i<MAX;i++) chk[i]=0;
sort(v,v+n,cmpy);
for(ll i=1,pt=0;i<n;i++){
if(v[i-1].y==v[i].y){
for(;pt<iycp.size();pt++){
if(iycp[pt]>v[i].y) break;
for(ll j=0;j<ey[pt].size();j++) {
if(chk[ey[pt][j]]) pos.erase(pos.lower_bound(h[ey[pt][j]].x1)),pos.erase(pos.lower_bound(h[ey[pt][j]].x2-1));
else pos.insert(h[ey[pt][j]].x1),pos.insert(h[ey[pt][j]].x2-1);
chk[ey[pt][j]]=!chk[ey[pt][j]];
}
}
if(!exist(v[i-1].x,v[i].x)){
ll dist=v[i].x-v[i-1].x;
conn[v[i].idx].push_back(make_pair(v[i-1].idx,dist));
conn[v[i-1].idx].push_back(make_pair(v[i].idx,dist));
}
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<conn[i].size();j++) {
if(i<conn[i][j].x) mst.push_back({i,conn[i][j].x,conn[i][j].y});
}
}
for(ll i=0;i<n;i++) par[i]=i;
sort(mst.begin(),mst.end());
val.push_back(0),val2.push_back(0);
for(ll i=0;i<mst.size();i++){
if(fnd(mst[i].x)!=fnd(mst[i].y)) cum+=mst[i].d, val.push_back(cum), val2.push_back(mst[i].d), uni(mst[i].x,mst[i].y);
}
vector<ll>::iterator it;
for(ll i=0;i<c;i++){
ll t1,t2;
scanf("%lld%lld",&t1,&t2);
if(n>=t2+val.size()){
printf("-1\n");
}
else{
it=lower_bound(val2.begin(),val2.end(),t1);
ll idx=max((ll)(it-val2.begin()-1),n-t2);
printf("%lld\n",val[idx]+t1*(n-idx));
}
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;pt<ixcp.size();pt++){
~~^~~~~~~~~~~~
construction.cpp:74:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<ex[pt].size();j++) {
~^~~~~~~~~~~~~~
construction.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;pt<iycp.size();pt++){
~~^~~~~~~~~~~~
construction.cpp:94:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<ey[pt].size();j++) {
~^~~~~~~~~~~~~~
construction.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<conn[i].size();j++) {
~^~~~~~~~~~~~~~~
construction.cpp:116:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i<mst.size();i++){
~^~~~~~~~~~~
construction.cpp:124:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(n>=t2+val.size()){
~^~~~~~~~~~~~~~~
construction.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&n,&m,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:54:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(ll i=0;i<n;i++){scanf("%lld%lld",&v[i].x,&v[i].y),v[i].idx=i;}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
construction.cpp:55:96: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(ll i=0;i<m;i++){scanf("%lld%lld%lld%lld",&h[i].x1,&h[i].y1,&h[i].x2,&h[i].y2),h[i].x2++,h[i].y2++;}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
construction.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&t1,&t2);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
34452 KB |
Output is correct |
| 2 |
Correct |
264 ms |
49952 KB |
Output is correct |
| 3 |
Correct |
253 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
418 ms |
70608 KB |
Output is correct |
| 5 |
Correct |
344 ms |
70608 KB |
Output is correct |
| 6 |
Correct |
272 ms |
70608 KB |
Output is correct |
| 7 |
Correct |
277 ms |
71140 KB |
Output is correct |
| 8 |
Correct |
282 ms |
71140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1583 ms |
79084 KB |
Output is correct |
| 2 |
Correct |
1510 ms |
79108 KB |
Output is correct |
| 3 |
Correct |
1559 ms |
79108 KB |
Output is correct |
| 4 |
Correct |
1519 ms |
79108 KB |
Output is correct |
| 5 |
Correct |
858 ms |
79108 KB |
Output is correct |
| 6 |
Correct |
319 ms |
79108 KB |
Output is correct |
| 7 |
Correct |
1575 ms |
94608 KB |
Output is correct |
| 8 |
Correct |
640 ms |
116960 KB |
Output is correct |
| 9 |
Correct |
647 ms |
124300 KB |
Output is correct |
| 10 |
Correct |
867 ms |
142160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
556 ms |
142160 KB |
Output is correct |
| 2 |
Correct |
570 ms |
142160 KB |
Output is correct |
| 3 |
Correct |
515 ms |
142160 KB |
Output is correct |
| 4 |
Correct |
624 ms |
142160 KB |
Output is correct |
| 5 |
Correct |
430 ms |
142160 KB |
Output is correct |
| 6 |
Correct |
643 ms |
142160 KB |
Output is correct |
| 7 |
Correct |
591 ms |
142160 KB |
Output is correct |
| 8 |
Correct |
559 ms |
142160 KB |
Output is correct |
| 9 |
Correct |
519 ms |
142160 KB |
Output is correct |
| 10 |
Correct |
571 ms |
142160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1818 ms |
142160 KB |
Output is correct |
| 2 |
Correct |
1014 ms |
142160 KB |
Output is correct |
| 3 |
Correct |
1814 ms |
142160 KB |
Output is correct |
| 4 |
Correct |
420 ms |
142160 KB |
Output is correct |
| 5 |
Correct |
1729 ms |
142160 KB |
Output is correct |
| 6 |
Correct |
447 ms |
142160 KB |
Output is correct |
| 7 |
Correct |
1543 ms |
142160 KB |
Output is correct |
| 8 |
Correct |
1840 ms |
142160 KB |
Output is correct |
| 9 |
Correct |
941 ms |
142160 KB |
Output is correct |
| 10 |
Correct |
1099 ms |
145444 KB |
Output is correct |
| 11 |
Correct |
614 ms |
145444 KB |
Output is correct |
