Submission #386295

#	Time	Username	Problem	Language	Result	Execution time	Memory
386295		kshitij_sodani	Road Construction (JOI21_road_construction)	C++14	100 / 100	3097 ms	565084 KiB

road_construction

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n,k;
llo aa[300001];
llo bb[300001];
pair<llo,llo> tree[30*600001];
llo ll[30*700001];
llo rr[30*700001];
pair<llo,llo> le[300001];
llo mm[3000001];
pair<llo,llo> re[300001];
llo nn[3000001];
vector<pair<llo,llo>> ss;
llo cur=0;
llo build(llo l,llo r){
	llo cot=cur;
	cur++;
	if(l==r){
		tree[cot]={(llo)1e18,l};
		return cot;
	}
	else{
		llo mid=(l+r)/2;
		ll[cot]=build(l,mid);
		rr[cot]=build(mid+1,r);
		
		if(tree[ll[cot]].a<=tree[rr[cot]].a){
			tree[cot]=tree[ll[cot]];
		}
		else{
			tree[cot]=tree[rr[cot]];
		}
		return cot;
	}
}
llo update(llo no,llo l,llo r,llo i,llo val){
	llo cot=cur;
	cur++;
	if(l==r){
		tree[cot]={val,l};
	}
	else{
		ll[cot]=ll[no];
		rr[cot]=rr[no];
		llo mid=(l+r)/2;
		if(i<=mid){
			ll[cot]=update(ll[cot],l,mid,i,val);
		}
		else{
			rr[cot]=update(rr[cot],mid+1,r,i,val);
		}
		if(tree[ll[cot]].a<=tree[rr[cot]].a){
			tree[cot]=tree[ll[cot]];
		}
		else{
			tree[cot]=tree[rr[cot]];
		}
	}
	return cot;
}
pair<llo,llo> query(llo no,llo l,llo r,llo aa,llo bb){
	if(aa>bb or r<aa or l>bb){
		return {1e18,-1}; 
	}
	else if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		pair<llo,llo> xx=query(ll[no],l,mid,aa,bb);
		pair<llo,llo> yy=query(rr[no],mid+1,r,aa,bb);
		if(xx.a<=yy.a){
			return xx;
		}
		else{
			return yy;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(llo i=0;i<n;i++){
		cin>>aa[i];
		cin>>bb[i];
		ss.pb({aa[i],-bb[i]});
	}
	sort(ss.begin(),ss.end());
	for(int i=0;i<ss.size();i++){
		ss[i].b=-ss[i].b;
	}
	/*vector<int> tt;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			tt.pb(abs(aa[i]-aa[j])+abs(bb[i]-bb[j]));
		}
	}
	sort(tt.begin(),tt.end());*/
	/*for(int i=0;i<n;i++){
		cout<<ss[i].a<<","<<ss[i].b<<endl;
	}*/
	/*for(int i=0;i<k;i++){
		cout<<tt[i]<<" ";
	}
	cout<<endl;*/
	map<llo,llo> ind3;
	for(llo i=0;i<n;i++){
		ind3[ss[i].a]=i;
	}
	llo r1=build(0,n-1);//-x+y
	llo r2=build(0,n-1);//x+y;
	vector<pair<pair<llo,llo>,llo>> yy;

	for(llo i=0;i<n;i++){
		yy.pb({{-ss[i].b,ss[i].a},i});
	}
	sort(yy.begin(),yy.end());
	for(int j=0;j<yy.size();j++){
		yy[j].a.a=-yy[j].a.a;
	}
	vector<pair<pair<llo,llo>,llo>> root;
	root.pb({{r1,r2},((llo)1e18)});
	map<llo,llo> ind;
	map<llo,llo> ind2;
	llo co=0;
	for(auto j:yy){
		co++;
		r1=update(r1,0,n-1,j.b,-j.a.b+j.a.a);
	//	cout<<j.b<<"<<"<<-j.a.b+j.a.a<<endl;
		r2=update(r2,0,n-1,j.b,j.a.b+j.a.a);
		root.pb({{r1,r2},j.a.a});
		if(ind.find(j.a.a)==ind.end()){
			ind[j.a.a]=co;
		}
		ind2[j.a.a]=co;
	}
	/*for(auto j:root){
		cout<<j.a.a<<",,"<<j.a.b<<",,"<<j.b<<endl;
	}
	cout<<endl;*/
	//cout<<ind2[2]<<endl;
	priority_queue<pair<llo,llo>> xx;
	llo xy=0;
	/*for(auto j:yy){
		cout<<j.a.a<<","<<j.a.b<<":"<<j.b<<endl;
	}
	cout<<endl;*/
	for(auto j:yy){
		le[xy]=query(root[ind2[j.a.a]].a.a,0,n-1,0,j.b-1);
		
		le[xy].a+=j.a.b-j.a.a;;
		mm[xy]=root[ind2[j.a.a]].a.a;
		re[xy]=query(root[ind[j.a.a]-1].a.b,0,n-1,ind3[j.a.b]+1,n-1);
		re[xy].a-=(j.a.a+j.a.b);
		

		nn[xy]=root[ind[j.a.a]-1].a.b;
		//cout<<j.a.a<<","<<j.a.b<<":"<<j.b<<endl;
		//cout<<ind2[j.a.a]<<"::"<<0<<"::"<<j.b-1<<endl;
	//	cout<<le[xy].a<<":"<<re[xy].a<<endl;
	//	cout<<le[xy].b<<"<<"<<endl;
		//cout<<endl;
		xx.push({-min(re[xy].a,le[xy].a),xy});
		
		xy++;

	}
	for(int i=0;i<k;i++){
		pair<llo,llo> no=xx.top();
		xx.pop();
		cout<<(-no.a)<<endl;
		xy=no.b;
		pair<pair<llo,llo>,llo> j=yy[no.b];

		if(le[no.b].a<=re[no.b].a){
			/*if(le[no.b].b==-1){
				while(true){
					continue;
				}
			}*/
			//cout<<11<<endl;
			mm[xy]=update(mm[xy],0,n-1,le[xy].b,(llo)1e18);
		
			le[xy]=query(mm[xy],0,n-1,0,j.b-1);
			le[xy].a+=j.a.b-j.a.a;;
			//cout<<le[xy].a<<"<<"<<endl;
		}
		else{
			/*if(re[no.b].b==-1){
				while(true){
					continue;
				}
			}*/
			//cout<<11<<endl;
			nn[xy]=update(nn[xy],0,n-1,re[xy].b,(llo)1e18);
			re[xy]=query(nn[xy],0,n-1,ind3[j.a.b]+1,n-1);
			re[xy].a-=(j.a.a+j.a.b);
		}
		//cout<<no.b<<":"<<re[no.b].a<<":"<<le[j.b].a<<endl;
		xx.push({-min(re[no.b].a,le[no.b].a),xy});
	}



 
	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:99:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
road_construction.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int j=0;j<yy.size();j++){
      |              ~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35