Submission #522635

#	Time	Username	Problem	Language	Result	Execution time	Memory
522635		nathanlee726	Road Construction (JOI21_road_construction)	C++14	100 / 100	9510 ms	95656 KiB

road_construction

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;

//#undef LOCAL
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

int n,k,ind=0,rd[250010];
pii pt[250010];
multiset<signed> st[250010];

struct TREAP{
	int l,r,pr,v,c,si;
	TREAP():l(-1),r(-1),pr(-1),v(-1),c(0),si(0){} 
}treap[250010],treap1[250010];

void pull(int p){
	int ss=treap[p].c;
	if(treap[p].l!=-1)ss+=treap[treap[p].l].si;
	if(treap[p].r!=-1)ss+=treap[treap[p].r].si;
	treap[p].si=ss;
}

int merge(int a,int b){
	if(a==-1||b==-1){
		if(a==-1)return b;
		else return a;
	}
	if(treap[a].pr>treap[b].pr){
		treap[a].r=merge(treap[a].r,b);
		pull(a);
		return a;
	}
	else{
		treap[b].l=merge(a,treap[b].l);
		pull(b);
		return b;
	}
}

pii split(int a,int x){
	if(a==-1)return{-1,-1};
	if(treap[a].v<=x){
		pii tp=split(treap[a].r,x);
		treap[a].r=tp.X;
		pull(a);
		return {a,tp.Y};
	}
	else{
		pii tp=split(treap[a].l,x);
		treap[a].l=tp.Y;
		pull(a);
		return {tp.X,a};
	}
}

int insert(int a,int x){
	if(a==-1){
		treap[ind].v=x;
		treap[ind].c=treap[ind].si=1;
		treap[ind].pr=rd[ind];
		int pp=ind++;
		return pp;
	}
	pii pt1=split(a,x);
	pii pt2=split(pt1.X,x-1);
	if(pt2.Y!=-1){
		treap[pt2.Y].c++;
		treap[pt2.Y].si=treap[pt2.Y].c;
		return merge(merge(pt2.X,pt2.Y),pt1.Y);
	}
	else{
		treap[ind].v=x;
		treap[ind].c=treap[ind].si=1;
		treap[ind].pr=rd[ind];
		int re=merge(merge(pt2.X,ind),pt1.Y);
		ind++;
		return re;	
	}
}

int remove(int a,int x){
	//bug(a,x);
	pii pt1=split(a,x);
	pii pt2=split(pt1.X,x-1);
	if(treap[pt2.Y].si==1){
		treap[pt2.Y].si--;
		treap[pt2.Y].c--;
		return merge(pt2.X,pt1.Y);
	}
	else{
		//assert(treap[pt2.Y].si>1);
		treap[pt2.Y].si--;
		treap[pt2.Y].c--;
		return merge(merge(pt2.X,pt2.Y),pt1.Y);
	}
}

int getv(int a,int x){
	if(a==-1)return 0;
	int sl=(treap[a].l==-1?0:treap[treap[a].l].si);
	if(x>=treap[a].v)return getv(treap[a].r,x)+sl+treap[a].c;
	else return getv(treap[a].l,x);
}
////////
vector<pii> v;

void pull1(int p){
	int ss=treap1[p].c;
	if(treap1[p].l!=-1)ss+=treap1[treap[p].l].si;
	if(treap1[p].r!=-1)ss+=treap1[treap[p].r].si;
	treap1[p].si=ss;
}

int merge1(int a,int b){
	if(a==-1||b==-1){
		if(a==-1)return b;
		else return a;
	}
	if(treap1[a].pr>treap1[b].pr){
		treap1[a].r=merge1(treap1[a].r,b);
		pull1(a);
		return a;
	}
	else{
		treap1[b].l=merge1(a,treap1[b].l);
		pull1(b);
		return b;
	}
}

pii split1(int a,int x){
	if(a==-1)return{-1,-1};
	if(treap1[a].v<=x){
		pii tp=split1(treap1[a].r,x);
		treap1[a].r=tp.X;
		pull1(a);
		return {a,tp.Y};
	}
	else{
		pii tp=split1(treap1[a].l,x);
		treap1[a].l=tp.Y;
		pull1(a);
		return {tp.X,a};
	}
}

int insert1(int a,int x,int rx){
	if(a==-1){
		treap1[ind].v=x;
		treap1[ind].c=treap1[ind].si=1;
		treap1[ind].pr=rd[ind];
		st[ind].insert(rx);
		int pp=ind++;
		return pp;
	}
	pii pt1=split1(a,x);
	pii pt2=split1(pt1.X,x-1);
	if(pt2.Y!=-1){
		treap1[pt2.Y].c++;
		treap1[pt2.Y].si=treap1[pt2.Y].c;
		st[pt2.Y].insert(rx);
		return merge1(merge1(pt2.X,pt2.Y),pt1.Y);
	}
	else{
		treap1[ind].v=x;
		treap1[ind].c=treap1[ind].si=1;
		treap1[ind].pr=rd[ind];
		st[ind].insert(rx);
		int re=merge1(merge1(pt2.X,ind),pt1.Y);
		ind++;
		return re;	
	}
}

int remove1(int a,int x,int rx){
	pii pt1=split1(a,x);
	pii pt2=split1(pt1.X,x-1);
	if(treap1[pt2.Y].si==1){
		treap1[pt2.Y].c--;
		treap1[pt2.Y].si--;
		st[pt2.Y].erase(st[pt2.Y].find(rx));
		return merge1(pt2.X,pt1.Y);
	}
	else{
		assert(treap1[pt2.Y].si>1);
		treap1[pt2.Y].si--;
		treap1[pt2.Y].c--;
		st[pt2.Y].erase(st[pt2.Y].find(rx));
		return merge1(merge1(pt2.X,pt2.Y),pt1.Y);
	}
}

void travel(int a){
	if(a==-1)return;
	travel(treap1[a].l);
	//bug(treap1[a].v,treap1[a].c,sz(st[a]));
	for(int i:st[a]){
		v.pb({i,treap1[a].v});
	} 
	travel(treap1[a].r);
}
////////

signed main(){
	IOS();
	//freopen("05-01.txt","r",stdin);
	cin>>n>>k;
	F(n){
		int x,y;
		cin>>x>>y;
		int xx,yy;
		xx=x+y;
		yy=x-y;
		pt[i]={xx,yy};
	}
	sort(pt,pt+n);
	F(250005)rd[i]=i;
	random_shuffle(rd,rd+250004);
	int rt=-1;
	int l=0,r=4e9;
	queue<pii> qu;
	while(l<r){
		int mi=(l+r)/2;
		int s=0;
		rt=-1,ind=0;
		F(n){
			while(!qu.empty()){
				if(qu.front().X>=pt[i].X-mi)break;
				rt=remove(rt,qu.front().Y);
				qu.pop();
			}
			if(rt!=-1){
				s+=getv(rt,pt[i].Y+mi)-getv(rt,pt[i].Y-mi-1);	
				//bug(treap[ppt1.Y].si,ppt1.Y);
			}
			rt=insert(rt,pt[i].Y);
			qu.push(pt[i]);
		}
		//bug(mi,s);
		while(!qu.empty()){
			rt=remove(rt,qu.front().Y);
			qu.pop();
		}
		if(s<k)l=mi+1;
		else r=mi;
	}
	int tk=l;
	ind=0;
	rt=-1;
	while(!qu.empty())qu.pop();
	multiset<int> sst;
	F(n){
		while(!qu.empty()){
			if(qu.front().X>=pt[i].X-tk)break;
			rt=remove1(rt,qu.front().Y,qu.front().X);
			qu.pop();
		}
		if(rt!=-1){
			pii ppt=split1(rt,pt[i].Y+tk);
			pii ppt1=split1(ppt.X,pt[i].Y-tk-1);
			v.clear();
			travel(ppt1.Y);
			//assert(sz(v)==treap1[ppt1.Y].si);
			//bug(sz(v),treap1[ppt1.Y].si);
			for(pii pi:v){
				sst.insert(max(abs(pi.X-pt[i].X),abs(pi.Y-pt[i].Y)));
			}
			rt=merge1(merge1(ppt1.X,ppt1.Y),ppt.Y);
		}
		rt=insert1(rt,pt[i].Y,pt[i].X);
		qu.push(pt[i]);
	}
	bug(tk);
	//F(n)bug(pt[i].X,pt[i].Y);
	int cc=0;
	for(int i:sst){
	cc++;
	cout<<i<<endl;
	if(cc==k)break;
	}
	return 0;
}

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