Submission #1157957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157957		dibamboo23	Road Construction (JOI21_road_construction)	C++20	13 / 100	1433 ms	381592 KiB

road_construction

/* author : Dinmukhammed ^_^ */																													

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define sz size()
#define ll long long
#define ld long double


const int N=3e5+3;
const ll inf=1e18;
const ll MOD=1e9+7;

ll t[N*60],L[N*60],R[N*60];

int iddd=0;
int n;

int copy(int v){
	int nv=++iddd;
	t[nv]=t[v];
	L[nv]=L[v];
	R[nv]=R[v];
	return nv;
}

int build(int tl=1,int tr=n){
	int v=++iddd;
	t[v]=inf;
	if(tl==tr)return v;
	int md=(tl+tr)>>1;
	L[v]=build(tl,md);
	R[v]=build(md+1,tr);
	return v;
}

int upd(int pos,ll x,int v,int tl=1,int tr=n){
	v=copy(v);
	if(tl==tr){
		t[v]=x;
		return v;
	}
	int md=(tl+tr)>>1;
	if(pos<=md)L[v]=upd(pos,x,L[v],tl,md);
	else R[v]=upd(pos,x,R[v],md+1,tr);
	t[v]=min(t[L[v]],t[R[v]]);
	return v;
}

ll get(int l,int r,int v,int tl=1,int tr=n){
	if(tl>=l&&tr<=r)return t[v];
	if(tl>r||l>tr)return inf;
	int md=(tl+tr)>>1;
	return min(get(l,r,L[v],tl,md),get(l,r,R[v],md+1,tr));
}

int del(ll x,int v,int tl=1,int tr=n){
	v=copy(v);
	if(tl==tr){
		t[v]=inf;
		return v;
	}
	int md=(tl+tr)>>1;
	if(t[R[v]]!=x)L[v]=del(x,L[v],tl,md);
	else R[v]=del(x,R[v],md+1,tr);
	t[v]=min(t[L[v]],t[R[v]]);
	return v;
}

int x[N],y[N],hh[N];

bool cmp(int i,int j){
	return x[i]<x[j];
}

void Main(){
	int k;cin>>n>>k;
	vector<int>st1,pos;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i],st1.push_back(y[i]),pos.push_back(i);
	sort(st1.begin(),st1.end());
	map<int,int>mp;
	int id=0;
	for(int i=0;i<n;i++){
		if(i==0||st1[i]!=st1[i-1])mp[st1[i]]=id;
		id++;
	}
	sort(pos.begin(),pos.end(),cmp);
	set<pair<ll,int>>st;
	id=0;
	vector<int>root1={build()};
	vector<int>root2={build()};
	for(auto i:pos){
		// cout<<x[i]<<" "<<y[i]<<" ";
		mp[y[i]]++;
		int h=mp[y[i]];
		// cout<<h<<"\n";
		hh[id]=h;
		ll val=min(get(1,h,root1.back())+(ll)x[i]+(ll)y[i],get(h,n,root2.back())+(ll)x[i]-(ll)y[i]);
		st.insert({val,id});
		root1.push_back(upd(h,-(ll)x[i]-(ll)y[i],root1.back()));
		root2.push_back(upd(h,-(ll)x[i]+(ll)y[i],root2.back()));
		id++;
	}
	// cout<<"\n";
	// for(auto to:st)cout<<to.F<<" "<<to.S<<"\n";
	// cout<<"\n";
	while(k--){
		cout<<st.begin()->F<<"\n";
		int v=st.begin()->S;
		ll val=st.begin()->F;
		st.erase(st.begin());
		int i=pos[v];
		ll val1=get(1,hh[v],root1[v]);
		ll val2=get(hh[v],n,root2[v]);
		if(val==val2+(ll)x[i]-(ll)y[i]){
			// cout<<"2";
			root2[v]=del(val2,root2[v]);
			val2=get(hh[v],n,root2[v]);
		}
		else if(val==val1+(ll)x[i]+(ll)y[i]){
			// cout<<"1";
			root1[v]=del(val1,root1[v]);
			val1=get(1,hh[v],root1[v]);
		}
		// cout<<val1<<" "<<val2<<"\n";
		if(min(val,val1)==inf)continue;
		ll res=min(val1+(ll)x[i]+(ll)y[i],val2+(ll)x[i]-(ll)y[i]);
		// cout<<res<<" "<<v<<"\n";
		st.insert({res,v});
	}
}



signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tt=1;
	// cin>>tt;
	while(tt--)Main(),cout<<"\n";
}

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