oj.uz

Submission #522635

# Submission time Handle Problem Language Result Execution time Memory
522635 2022-02-05T09:47:50 Z nathanlee726 Road Construction (JOI21_road_construction) C++14
100 / 100
 9510 ms 95656 KB 
//#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 51908 KB Output is correct
2 Correct 185 ms 51780 KB Output is correct
3 Correct 160 ms 51880 KB Output is correct
4 Correct 189 ms 51988 KB Output is correct
5 Correct 175 ms 50768 KB Output is correct
6 Correct 31 ms 37664 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2073 ms 54532 KB Output is correct
2 Correct 2001 ms 54572 KB Output is correct
3 Correct 160 ms 51780 KB Output is correct
4 Correct 1911 ms 56692 KB Output is correct
5 Correct 2186 ms 66236 KB Output is correct
6 Correct 2329 ms 66220 KB Output is correct
7 Correct 2230 ms 57736 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5179 ms 44680 KB Output is correct
2 Correct 5141 ms 44552 KB Output is correct
3 Correct 29 ms 37452 KB Output is correct
4 Correct 1938 ms 53180 KB Output is correct
5 Correct 5610 ms 65080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5179 ms 44680 KB Output is correct
2 Correct 5141 ms 44552 KB Output is correct
3 Correct 29 ms 37452 KB Output is correct
4 Correct 1938 ms 53180 KB Output is correct
5 Correct 5610 ms 65080 KB Output is correct
6 Correct 5195 ms 44584 KB Output is correct
7 Correct 5289 ms 44792 KB Output is correct
8 Correct 22 ms 37452 KB Output is correct
9 Correct 23 ms 37452 KB Output is correct
10 Correct 4950 ms 44496 KB Output is correct
11 Correct 1963 ms 53340 KB Output is correct
12 Correct 5407 ms 45620 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 51908 KB Output is correct
2 Correct 185 ms 51780 KB Output is correct
3 Correct 160 ms 51880 KB Output is correct
4 Correct 189 ms 51988 KB Output is correct
5 Correct 175 ms 50768 KB Output is correct
6 Correct 31 ms 37664 KB Output is correct
7 Correct 3626 ms 52780 KB Output is correct
8 Correct 3765 ms 52780 KB Output is correct
9 Correct 183 ms 51980 KB Output is correct
10 Correct 2523 ms 52144 KB Output is correct
11 Correct 1975 ms 51892 KB Output is correct
12 Correct 2128 ms 59712 KB Output is correct
13 Correct 2854 ms 52840 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 51908 KB Output is correct
2 Correct 185 ms 51780 KB Output is correct
3 Correct 160 ms 51880 KB Output is correct
4 Correct 189 ms 51988 KB Output is correct
5 Correct 175 ms 50768 KB Output is correct
6 Correct 31 ms 37664 KB Output is correct
7 Correct 2073 ms 54532 KB Output is correct
8 Correct 2001 ms 54572 KB Output is correct
9 Correct 160 ms 51780 KB Output is correct
10 Correct 1911 ms 56692 KB Output is correct
11 Correct 2186 ms 66236 KB Output is correct
12 Correct 2329 ms 66220 KB Output is correct
13 Correct 2230 ms 57736 KB Output is correct
14 Correct 5179 ms 44680 KB Output is correct
15 Correct 5141 ms 44552 KB Output is correct
16 Correct 29 ms 37452 KB Output is correct
17 Correct 1938 ms 53180 KB Output is correct
18 Correct 5610 ms 65080 KB Output is correct
19 Correct 5195 ms 44584 KB Output is correct
20 Correct 5289 ms 44792 KB Output is correct
21 Correct 22 ms 37452 KB Output is correct
22 Correct 23 ms 37452 KB Output is correct
23 Correct 4950 ms 44496 KB Output is correct
24 Correct 1963 ms 53340 KB Output is correct
25 Correct 5407 ms 45620 KB Output is correct
26 Correct 3626 ms 52780 KB Output is correct
27 Correct 3765 ms 52780 KB Output is correct
28 Correct 183 ms 51980 KB Output is correct
29 Correct 2523 ms 52144 KB Output is correct
30 Correct 1975 ms 51892 KB Output is correct
31 Correct 2128 ms 59712 KB Output is correct
32 Correct 2854 ms 52840 KB Output is correct
33 Correct 9510 ms 55220 KB Output is correct
34 Correct 9478 ms 60376 KB Output is correct
35 Correct 6505 ms 59660 KB Output is correct
36 Correct 5281 ms 95656 KB Output is correct
37 Correct 5311 ms 95504 KB Output is correct
38 Correct 6789 ms 66804 KB Output is correct