Submission #43319

#TimeUsernameProblemLanguageResultExecution timeMemory
43319ffresh도로 건설 사업 (JOI13_construction)C++14
0 / 100
1750 ms130812 KiB
#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)); } 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; } } } 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 (stderr)

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:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<vv[i].size();++j){
                ^
construction.cpp:130:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<id.size();++i){
               ^
construction.cpp:192:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<Edge.size();++i){
               ^
construction.cpp:207: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:214: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...