Submission #413808

#	Time	Username	Problem	Language	Result	Execution time	Memory
413808		keta_tsimakuridze	Road Construction (JOI21_road_construction)	C++14	100 / 100	3851 ms	505356 KiB

road_construction

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pii pair<int,int> 
using namespace std;
const int N=3e5+5,mod=1e9+7,Inf=7e9+16;
int t,n,k,le_[50*N],ri_[50*N],pos[N][2],K,cur,root[N],ind[N],I[N];
pair<int,int> tree[50*N][2];
pair<int,int>p[N];
set<pair<int,int> > s;
vector<pair<int,int> > v;
vector<pair<int,pair<int,int> > > c;
 
void build(int u,int l,int r){
tree[u][0] = tree[u][1] = {Inf,l}; 
	if(l==r) return;
	le_[u]=++cur;
	ri_[u]=++cur;
	int mid=(l+r)/2;
	build(le_[u],l,mid);
	build(ri_[u],mid+1,r);
	
}
void update(int u,int ind,int l,int r,int val1,int val2){
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[cur][0]={val1,l};
		tree[cur][1]={val2,l};
		return;
	}
	int mid = (l+r)/2,x = cur;
	le_[x]= le_[u];
	ri_[x] = ri_[u];
	if(ind<=mid) le_[x]=++cur;
	else ri_[x]=++cur;
	update(le_[u],ind,l,mid,val1,val2);
	update(ri_[u],ind,mid+1,r,val1,val2);
	tree[x][0]=min(tree[le_[x]][0],tree[ri_[x]][0]);
	tree[x][1]=min(tree[le_[x]][1],tree[ri_[x]][1]);
//	cout<<x<<"++"<<endl;
}
pair<int,int> getans(int u,int start,int end,int l,int r,int type){
	if(l>end|| r<start) return {Inf,0};
	if(start<=l && r<=end) { 
return tree[u][type];}
	int mid=(l+r)/2;
	
	return min(getans(le_[u],start,end,l,mid,type) , getans(ri_[u],start,end,mid+1,r,type)); 
}
main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin >> p[i].f>>p[i].s;
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++) {
		int diff = p[i].s;
		v.push_back({diff,i});
	}
	v.push_back({-5e9,0});
	sort(v.begin(),v.end());
	for(int i=1;i<=n;i++) {
		ind[v[i].s] = i; //cout<<v[i].s<<" ++ "<<i<<endl;
//		pos[i] = v[i].s;
	}
	cur=1;
	root[1] = cur;
	build(1,1,n);
	for(int i=1;i<=n;i++) {
 
		
		int l = 1,r=n,id = n+1;
		while(l<=r){
			int mid=(l+r)/2;
			if(v[mid].f>=p[i].s) {
				id = mid;
				r=mid-1;
			}else l=mid+1;
		}
		
		if(i-1)root[i] = ++cur;
		I[i] = id-1;
	//	cout<<id<<endl; // - y[i] +y[j] < -y[j] + y[i] y[j] < y[i]
		if(i-1)update(root[i-1],ind[i-1],1,n,-p[i-1].f-p[i-1].s,-p[i-1].f+p[i-1].s); 
		s.insert({min(getans(root[i],1,id-1,1,n,0).f +p[i].f+p[i].s,getans(root[i],id,n,1,n,1).f +p[i].f - p[i].s),i} );
//	cout<<"++"<<getans(root[i],id,n,1,n,1).f +p[i].f - p[i].s<<" "<<getans(root[i],id,n,1,n,1).s<<endl;
	} 
	while(k--){
		pii c = *s.begin();
		int i = c.s; 
	//	int g1 = getans(root[c.s],1,I[c.s],1,n,0).f+p[i].f+p[i].s, g2  = getans(root[c.s],I[c.s]+1,n,1,n,1);
		cout<<c.f<<endl;
		s.erase(c);
		int ind = 0; 
		if(getans(root[c.s],1,I[c.s],1,n,0).f+p[i].f+p[i].s < getans(root[c.s],I[c.s]+1,n,1,n,1).f  +p[i].f-p[i].s ) ind =getans(root[c.s],1,I[c.s],1,n,0).s;
		else  ind = getans(root[c.s],I[c.s]+1,n,1,n,1).s;
		int bef = root[c.s];
		root[c.s] = ++cur;
		update(bef,ind,1,n,Inf,Inf);
		s.insert({min(getans(root[i],1,I[i],1,n,0).f +p[i].f+p[i].s,getans(root[i],I[i]+1,n,1,n,1).f +p[i].f - p[i].s),c.s});
		//cout<<getans(root[i],1,I[i],1,n,0).f+p[i].f+p[i].s<<"++"<<getans(root[i],1,I[i],1,n,0).s<<endl;
	}
	
}

Compilation message (stderr)

road_construction.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~

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