oj.uz

답안 #522617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522617 2022-02-05T09:31:53 Z nathanlee726 Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 70264 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#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 195 ms 51852 KB Output is correct
2 Correct 188 ms 51848 KB Output is correct
3 Correct 230 ms 51960 KB Output is correct
4 Correct 184 ms 51992 KB Output is correct
5 Correct 184 ms 50816 KB Output is correct
6 Correct 33 ms 37604 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2390 ms 54532 KB Output is correct
2 Correct 2501 ms 57616 KB Output is correct
3 Correct 161 ms 51772 KB Output is correct
4 Correct 2287 ms 59820 KB Output is correct
5 Correct 2557 ms 69072 KB Output is correct
6 Correct 2577 ms 69260 KB Output is correct
7 Correct 2613 ms 60792 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6599 ms 44460 KB Output is correct
2 Correct 6440 ms 49520 KB Output is correct
3 Correct 27 ms 37468 KB Output is correct
4 Correct 2320 ms 56160 KB Output is correct
5 Correct 7134 ms 70264 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6599 ms 44460 KB Output is correct
2 Correct 6440 ms 49520 KB Output is correct
3 Correct 27 ms 37468 KB Output is correct
4 Correct 2320 ms 56160 KB Output is correct
5 Correct 7134 ms 70264 KB Output is correct
6 Correct 6299 ms 49788 KB Output is correct
7 Correct 7039 ms 49604 KB Output is correct
8 Correct 23 ms 37468 KB Output is correct
9 Correct 24 ms 37468 KB Output is correct
10 Correct 6798 ms 49560 KB Output is correct
11 Correct 2667 ms 56108 KB Output is correct
12 Correct 6897 ms 50788 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 51852 KB Output is correct
2 Correct 188 ms 51848 KB Output is correct
3 Correct 230 ms 51960 KB Output is correct
4 Correct 184 ms 51992 KB Output is correct
5 Correct 184 ms 50816 KB Output is correct
6 Correct 33 ms 37604 KB Output is correct
7 Correct 4212 ms 54900 KB Output is correct
8 Correct 4237 ms 54816 KB Output is correct
9 Correct 173 ms 51944 KB Output is correct
10 Correct 2804 ms 54172 KB Output is correct
11 Correct 2196 ms 53976 KB Output is correct
12 Correct 2455 ms 61840 KB Output is correct
13 Correct 3314 ms 55068 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 51852 KB Output is correct
2 Correct 188 ms 51848 KB Output is correct
3 Correct 230 ms 51960 KB Output is correct
4 Correct 184 ms 51992 KB Output is correct
5 Correct 184 ms 50816 KB Output is correct
6 Correct 33 ms 37604 KB Output is correct
7 Correct 2390 ms 54532 KB Output is correct
8 Correct 2501 ms 57616 KB Output is correct
9 Correct 161 ms 51772 KB Output is correct
10 Correct 2287 ms 59820 KB Output is correct
11 Correct 2557 ms 69072 KB Output is correct
12 Correct 2577 ms 69260 KB Output is correct
13 Correct 2613 ms 60792 KB Output is correct
14 Correct 6599 ms 44460 KB Output is correct
15 Correct 6440 ms 49520 KB Output is correct
16 Correct 27 ms 37468 KB Output is correct
17 Correct 2320 ms 56160 KB Output is correct
18 Correct 7134 ms 70264 KB Output is correct
19 Correct 6299 ms 49788 KB Output is correct
20 Correct 7039 ms 49604 KB Output is correct
21 Correct 23 ms 37468 KB Output is correct
22 Correct 24 ms 37468 KB Output is correct
23 Correct 6798 ms 49560 KB Output is correct
24 Correct 2667 ms 56108 KB Output is correct
25 Correct 6897 ms 50788 KB Output is correct
26 Correct 4212 ms 54900 KB Output is correct
27 Correct 4237 ms 54816 KB Output is correct
28 Correct 173 ms 51944 KB Output is correct
29 Correct 2804 ms 54172 KB Output is correct
30 Correct 2196 ms 53976 KB Output is correct
31 Correct 2455 ms 61840 KB Output is correct
32 Correct 3314 ms 55068 KB Output is correct
33 Execution timed out 10076 ms 49632 KB Time limit exceeded
34 Halted 0 ms 0 KB -