#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+15;
map<int,int> X,Y;
int vx[N],vy[N];
int dx[N],dy[N],ux[N],uy[N];
int xadj[N],yadj[N];
vector<pair<int,int> >vv[N];
int pen[N];
void update(int ind,int add){
assert(ind>0);
while(ind<N){
pen[ind]+=add;
ind += ind&(-ind);
}
}
int query(int ind){
int ret=0;
while(ind){
ret+=pen[ind];
ind = ind&(ind-1);
}
return ret;
}
int par[N];
int f(int x){
if(x==par[x])return x;
return par[x]= f(par[x]);
}
bool dead[N];
long long pre[N];
int main(){
//freopen("input.txt","r",stdin);
int n,m,c;
memset(xadj,-1,sizeof(xadj));
memset(yadj,-1,sizeof(yadj));
cin>>n>>m>>c;
vector<pair<int,pair<int,int> > >id;
for(int i=1;i<=n;++i){
scanf("%d%d",&vx[i],&vy[i]);
X[vx[i]];
Y[vy[i]];
id.push_back(make_pair(vx[i],make_pair(0,i)));
}
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&dx[i],&dy[i],&ux[i],&uy[i]);
X[dx[i]];
X[ux[i]];
Y[dy[i]];
Y[uy[i]];
id.push_back(make_pair(dx[i],make_pair(-1,i)));
id.push_back(make_pair(ux[i],make_pair(1,i)));
}
map<int,int>::iterator it;
int xpos=1,ypos=1;
for(it= X.begin();it!= X.end();++it)
it->second = xpos++;
for(it= Y.begin();it!= Y.end();++it)
it->second = ypos++;
for(int i=1;i<=n;++i){
vv[X[vx[i]]].push_back(make_pair(vy[i],i));
}
for(int i=0;i<N;++i){
sort(vv[i].begin(),vv[i].end());
for(int j=1;j<vv[i].size();++j){
xadj[vv[i][j].second]= (vv[i][j-1].second);
}
vv[i].clear();
}
for(int i=1;i<=n;++i){
vv[Y[vy[i]]].push_back(make_pair(vx[i],i));
}
for(int i=0;i<N;++i){
sort(vv[i].begin(),vv[i].end());
for(int j=1;j<vv[i].size();++j){
yadj[vv[i][j].second]= (vv[i][j-1].second);
}
vv[i].clear();
}
for(int i=1;i<=m;++i){
vv[X[dx[i]]].push_back(make_pair(dy[i],-1));
vv[X[dx[i]]].push_back(make_pair(uy[i],1e9));
vv[X[ux[i]]].push_back(make_pair(dy[i],-1));
vv[X[ux[i]]].push_back(make_pair(uy[i],1e9));
}
for(int i=1;i<=n;++i){
vv[X[vx[i]]].push_back(make_pair(vy[i],i));
}
for(int i=0;i<N;++i){
sort(vv[i].begin(),vv[i].end());
int cc=0;
for(int j=0;j<vv[i].size();++j){
if(vv[i][j].second==-1)++cc;
else if(vv[i][j].second==1e9)--cc;
else{
if(cc>0)
dead[vv[i][j].second]= 1;
}
}
vv[i].clear();
}
for(int i=1;i<=m;++i){
vv[Y[dy[i]]].push_back(make_pair(dx[i],-1));
vv[Y[dy[i]]].push_back(make_pair(ux[i],1e9));
vv[Y[uy[i]]].push_back(make_pair(dx[i],-1));
vv[Y[uy[i]]].push_back(make_pair(ux[i],1e9));
}
for(int i=1;i<=n;++i){
vv[Y[vy[i]]].push_back(make_pair(vx[i],i));
}
for(int i=0;i<N;++i){
sort(vv[i].begin(),vv[i].end());
int cc=0;
for(int j=0;j<vv[i].size();++j){
if(vv[i][j].second==-1)++cc;
else if(vv[i][j].second==1e9)--cc;
else{
if(cc>0)
dead[vv[i][j].second]= 1;
}
}
}
sort(id.begin(),id.end());
set<pair<int,int> > yind;
set<pair<int,int> >::iterator sit;
int iid;
vector<pair<int,pair<int,int> > >Edge;
for(int i=0;i<id.size();++i){
iid = id[i].second.second;
if(id[i].second.first==-1){
int yy = dy[iid],yy2 = uy[iid];
while(yind.size()>0){
sit = yind.lower_bound(make_pair(yy,0));
if(sit==yind.end() || (*sit).first>yy2)break;
yind.erase(sit);
}
yy = Y[yy],yy2 = Y[yy2];
update(yy,1);
update(yy2,1);
}
else if(id[i].second.first==0){
if(dead[iid])continue;
if(yadj[iid]!=-1){
int iid2 = yadj[iid];
if(yind.count(make_pair(vy[iid2],iid2))){
yind.erase(make_pair(vy[iid2],iid2));
Edge.push_back(make_pair(vx[iid]-vx[iid2],make_pair(iid2,iid)));
}
}
if(xadj[iid]!=-1){
int iid2= xadj[iid];
int R = query(Y[vy[iid]])- query(Y[vy[iid2]]-1);
if(R==0){
Edge.push_back(make_pair(vy[iid]-vy[iid2],make_pair(iid,iid2)));
}
}
yind.insert(make_pair(vy[iid],iid));
}
else{
int yy = dy[iid],yy2 = uy[iid];
while(yind.size()>0){
sit = yind.lower_bound(make_pair(yy,0));
if(sit==yind.end() || (*sit).first>yy2)break;
yind.erase(sit);
}
yy = Y[yy],yy2 = Y[yy2];
update(yy,-1);
update(yy2,-1);
}
}
sort(Edge.begin(),Edge.end());
vector<int> sum;
for(int i=1;i<=n;++i)par[i]= i;
int a,b;
long long orgs= 0;
for(int i=0;i<Edge.size();++i){
a= Edge[i].second.first, b= Edge[i].second.second;
if(f(a)!=f(b)){
sum.push_back(Edge[i].first);
orgs+=Edge[i].first;
par[f(b)]= f(a);
}
}
int comp = 0;
for(int i=1;i<=n;++i)
if(f(i)==i)
++comp;
reverse(sum.begin(),sum.end());
for(int i=1;i<=sum.size();++i){
pre[i]= pre[i-1] + sum[i-1];
}
int B,H;
while(c--){
scanf("%d%d",&B,&H);
if(comp>H){
printf("-1\n");
}
else{
int l= 1,r = min(H-comp,(int)sum.size()),mid;
if(sum.size()==0 || sum[0]<=B || r==0){
printf("%lld\n",orgs+ comp*B);
}
else{
while(l<r){
mid = (l+r+1)/2;
if(sum[mid-1]>B)
l = mid;
else
r = mid-1;
}
printf("%lld\n",orgs+ (long long)l*B -pre[l] + comp*B);
}
}
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<vv[i].size();++j){
^
construction.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<vv[i].size();++j){
^
construction.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vv[i].size();++j){
^
construction.cpp:136:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vv[i].size();++j){
^
construction.cpp:152:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<id.size();++i){
^
construction.cpp:213:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Edge.size();++i){
^
construction.cpp:229:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=sum.size();++i){
^
construction.cpp:56:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&vx[i],&vy[i]);
^
construction.cpp:62:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&dx[i],&dy[i],&ux[i],&uy[i]);
^
construction.cpp:236:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&B,&H);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
8696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1607 ms |
130804 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1501 ms |
130804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1634 ms |
130804 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
