Submission #43318

#	Time	Username	Problem	Language	Result	Execution time	Memory
43318		ffresh	도로 건설 사업 (JOI13_construction)	C++14	0 / 100	1668 ms	130716 KiB

construction

#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 alive[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();
	}

	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(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:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<vv[i].size();++j){
                ^
construction.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<vv[i].size();++j){
                ^
construction.cpp:107:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<id.size();++i){
               ^
construction.cpp:168:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<Edge.size();++i){
               ^
construction.cpp:183: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:190:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&B,&H);
                      ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30