oj.uz

답안 #522628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522628 2022-02-05T09:39:10 Z nathanlee726 Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 70172 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);
	}
}
////////
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){
				pii ppt=split(rt,pt[i].Y+mi);
				pii ppt1=split(ppt.X,pt[i].Y-mi-1);
				s+=treap[ppt1.Y].si;	
				//bug(treap[ppt1.Y].si,ppt1.Y);
				rt=merge(merge(ppt1.X,ppt1.Y),ppt.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

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 51780 KB Output is correct
2 Correct 196 ms 51876 KB Output is correct
3 Correct 173 ms 52120 KB Output is correct
4 Correct 163 ms 51908 KB Output is correct
5 Correct 167 ms 50708 KB Output is correct
6 Correct 33 ms 37684 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2317 ms 54504 KB Output is correct
2 Correct 2271 ms 57584 KB Output is correct
3 Correct 141 ms 51872 KB Output is correct
4 Correct 2129 ms 59664 KB Output is correct
5 Correct 2434 ms 69248 KB Output is correct
6 Correct 2434 ms 69292 KB Output is correct
7 Correct 2429 ms 61240 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5903 ms 44552 KB Output is correct
2 Correct 6056 ms 49740 KB Output is correct
3 Correct 21 ms 37452 KB Output is correct
4 Correct 2194 ms 56100 KB Output is correct
5 Correct 6887 ms 70172 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5903 ms 44552 KB Output is correct
2 Correct 6056 ms 49740 KB Output is correct
3 Correct 21 ms 37452 KB Output is correct
4 Correct 2194 ms 56100 KB Output is correct
5 Correct 6887 ms 70172 KB Output is correct
6 Correct 6229 ms 49800 KB Output is correct
7 Correct 6248 ms 49512 KB Output is correct
8 Correct 22 ms 37452 KB Output is correct
9 Correct 22 ms 37432 KB Output is correct
10 Correct 5901 ms 49624 KB Output is correct
11 Correct 2268 ms 56084 KB Output is correct
12 Correct 6938 ms 50856 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 51780 KB Output is correct
2 Correct 196 ms 51876 KB Output is correct
3 Correct 173 ms 52120 KB Output is correct
4 Correct 163 ms 51908 KB Output is correct
5 Correct 167 ms 50708 KB Output is correct
6 Correct 33 ms 37684 KB Output is correct
7 Correct 4613 ms 54848 KB Output is correct
8 Correct 4281 ms 54864 KB Output is correct
9 Correct 169 ms 51928 KB Output is correct
10 Correct 2773 ms 54216 KB Output is correct
11 Correct 2134 ms 54072 KB Output is correct
12 Correct 2410 ms 61792 KB Output is correct
13 Correct 3331 ms 55056 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 51780 KB Output is correct
2 Correct 196 ms 51876 KB Output is correct
3 Correct 173 ms 52120 KB Output is correct
4 Correct 163 ms 51908 KB Output is correct
5 Correct 167 ms 50708 KB Output is correct
6 Correct 33 ms 37684 KB Output is correct
7 Correct 2317 ms 54504 KB Output is correct
8 Correct 2271 ms 57584 KB Output is correct
9 Correct 141 ms 51872 KB Output is correct
10 Correct 2129 ms 59664 KB Output is correct
11 Correct 2434 ms 69248 KB Output is correct
12 Correct 2434 ms 69292 KB Output is correct
13 Correct 2429 ms 61240 KB Output is correct
14 Correct 5903 ms 44552 KB Output is correct
15 Correct 6056 ms 49740 KB Output is correct
16 Correct 21 ms 37452 KB Output is correct
17 Correct 2194 ms 56100 KB Output is correct
18 Correct 6887 ms 70172 KB Output is correct
19 Correct 6229 ms 49800 KB Output is correct
20 Correct 6248 ms 49512 KB Output is correct
21 Correct 22 ms 37452 KB Output is correct
22 Correct 22 ms 37432 KB Output is correct
23 Correct 5901 ms 49624 KB Output is correct
24 Correct 2268 ms 56084 KB Output is correct
25 Correct 6938 ms 50856 KB Output is correct
26 Correct 4613 ms 54848 KB Output is correct
27 Correct 4281 ms 54864 KB Output is correct
28 Correct 169 ms 51928 KB Output is correct
29 Correct 2773 ms 54216 KB Output is correct
30 Correct 2134 ms 54072 KB Output is correct
31 Correct 2410 ms 61792 KB Output is correct
32 Correct 3331 ms 55056 KB Output is correct
33 Execution timed out 10023 ms 49640 KB Time limit exceeded
34 Halted 0 ms 0 KB -