oj.uz

Submission #961750

# Submission time Handle Problem Language Result Execution time Memory
961750 2024-04-12T12:05:20 Z LCJLY Road Construction (JOI21_road_construction) C++14
100 / 100
 8803 ms 50596 KB 
#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;

int fw[1000005];
int n,k;

void upd(int x, int y){
	while(x<1000005){
		fw[x]+=y;
		x+=x&(-x);
	}
}

int sum(int x){	
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}	
	return counter;
}

void rangeUpd(int x, int y, int c){
	x=max(x,1LL);
	y=min(y,1000000LL);
	upd(x,c);
	upd(y+1,-c);
}

void solve(){
	cin >> n >> k;
	pii arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
		int a=arr[x].first+arr[x].second;
		int b=arr[x].first-arr[x].second;
		arr[x].first=a;
		arr[x].second=b;
		//show2(a,a,b,b);
	}
	
	sort(arr,arr+n);
	
	int l=0;
	int r=4e9;
	int mid;
	int best=r;
	while(l<=r){
		//show2(l,l,r,r);
		mid=(l+r)/2;
		
		int counter=0;
		
		vector<array<int,4>>v;
		vector<int>dis;
		for(int x=0;x<n;x++){
			int a=arr[x].first;
			int b=arr[x].second;
			v.push_back({a-mid,0,b-mid,b+mid});
			v.push_back({a,1,b,b});
			dis.push_back(b-mid);
			dis.push_back(b+mid);
			dis.push_back(b);
		}
		sort(v.begin(),v.end());
		//for(auto it:v){
			//cout << it[0] << " " << it[1] << " " << it[2] << " " << it[3] << endl;
		//}
		sort(dis.begin(),dis.end());
		dis.resize(unique(dis.begin(),dis.end())-dis.begin());
		int ptr=0;
		memset(fw,0,sizeof(fw));
		int sz=v.size();
		
		//show4(dis,dis);
		
		for(int x=0;x<sz;x++){
			v[x][2]=lower_bound(dis.begin(),dis.end(),v[x][2])-dis.begin()+1;
			v[x][3]=lower_bound(dis.begin(),dis.end(),v[x][3])-dis.begin()+1;
			//show3(v[x][1],v[x][1],v[x][2],v[x][2],v[x][3],v[x][3]);
			while(ptr<sz&&v[x][0]-2*mid>v[ptr][0]){
				if(v[ptr][1]==0){
					rangeUpd(v[ptr][2],v[ptr][3],-1);
				}
				ptr++;
			}
			
			if(v[x][1]==0){
				rangeUpd(v[x][2],v[x][3],1);
			}
			else{
				counter+=sum(v[x][2]);
			}
			//show(counter,counter);
		}
		
		counter=(counter-n)/2;
		//show(counter,counter);
		
		if(counter>=k){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	//show(best,best);
	
	vector<int>ans;
	multiset<pii>se;
	int ptr2=0;
	for(int x=0;x<n;x++){
		while(ptr2<n&&arr[ptr2].first<arr[x].first-best){
			se.erase(se.find({arr[ptr2].second,arr[ptr2].first}));
			ptr2++;
		}
		
		//show3(x,x,arr[x].first,arr[x].first,arr[x].second,arr[x].second);
		auto rt=se.lower_bound({arr[x].second,1e15});
		auto cur=rt;
		while(cur!=se.end()){
			pii hold=*cur;
			if(hold.first>arr[x].second+best) break;
			ans.push_back(max(abs(hold.first-arr[x].second),abs(hold.second-arr[x].first)));
			//show2(hold.first,hold.first,hold.second,hold.second);
			cur++;
		}
		cur=rt;
		while(cur!=se.begin()){
			cur--;
			pii hold=*cur;
			if(hold.first<arr[x].second-best) break;
			ans.push_back(max(abs(hold.first-arr[x].second),abs(hold.second-arr[x].first)));
			//show2(hold.first,hold.first,hold.second,hold.second);
		}
		se.insert({arr[x].second,arr[x].first});
	}
	
	sort(ans.begin(),ans.end());
	for(int x=0;x<k;x++){
		cout << ans[x] << "\n";
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 12904 KB Output is correct
2 Correct 62 ms 12900 KB Output is correct
3 Correct 55 ms 12996 KB Output is correct
4 Correct 52 ms 12996 KB Output is correct
5 Correct 58 ms 11712 KB Output is correct
6 Correct 21 ms 8280 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4280 ms 48300 KB Output is correct
2 Correct 4442 ms 48072 KB Output is correct
3 Correct 49 ms 12696 KB Output is correct
4 Correct 4242 ms 47288 KB Output is correct
5 Correct 4045 ms 47308 KB Output is correct
6 Correct 3958 ms 47300 KB Output is correct
7 Correct 4149 ms 47528 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8124 ms 49484 KB Output is correct
2 Correct 8067 ms 49340 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Correct 3928 ms 47260 KB Output is correct
5 Correct 5087 ms 50400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8124 ms 49484 KB Output is correct
2 Correct 8067 ms 49340 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Correct 3928 ms 47260 KB Output is correct
5 Correct 5087 ms 50400 KB Output is correct
6 Correct 7871 ms 49756 KB Output is correct
7 Correct 7772 ms 50176 KB Output is correct
8 Correct 6 ms 8280 KB Output is correct
9 Correct 6 ms 8284 KB Output is correct
10 Correct 7664 ms 50040 KB Output is correct
11 Correct 3963 ms 47600 KB Output is correct
12 Correct 5047 ms 49912 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 12904 KB Output is correct
2 Correct 62 ms 12900 KB Output is correct
3 Correct 55 ms 12996 KB Output is correct
4 Correct 52 ms 12996 KB Output is correct
5 Correct 58 ms 11712 KB Output is correct
6 Correct 21 ms 8280 KB Output is correct
7 Correct 3163 ms 27284 KB Output is correct
8 Correct 3189 ms 28428 KB Output is correct
9 Correct 55 ms 12940 KB Output is correct
10 Correct 3052 ms 28080 KB Output is correct
11 Correct 2902 ms 28164 KB Output is correct
12 Correct 1950 ms 26676 KB Output is correct
13 Correct 2105 ms 26812 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 12904 KB Output is correct
2 Correct 62 ms 12900 KB Output is correct
3 Correct 55 ms 12996 KB Output is correct
4 Correct 52 ms 12996 KB Output is correct
5 Correct 58 ms 11712 KB Output is correct
6 Correct 21 ms 8280 KB Output is correct
7 Correct 4280 ms 48300 KB Output is correct
8 Correct 4442 ms 48072 KB Output is correct
9 Correct 49 ms 12696 KB Output is correct
10 Correct 4242 ms 47288 KB Output is correct
11 Correct 4045 ms 47308 KB Output is correct
12 Correct 3958 ms 47300 KB Output is correct
13 Correct 4149 ms 47528 KB Output is correct
14 Correct 8124 ms 49484 KB Output is correct
15 Correct 8067 ms 49340 KB Output is correct
16 Correct 6 ms 8284 KB Output is correct
17 Correct 3928 ms 47260 KB Output is correct
18 Correct 5087 ms 50400 KB Output is correct
19 Correct 7871 ms 49756 KB Output is correct
20 Correct 7772 ms 50176 KB Output is correct
21 Correct 6 ms 8280 KB Output is correct
22 Correct 6 ms 8284 KB Output is correct
23 Correct 7664 ms 50040 KB Output is correct
24 Correct 3963 ms 47600 KB Output is correct
25 Correct 5047 ms 49912 KB Output is correct
26 Correct 3163 ms 27284 KB Output is correct
27 Correct 3189 ms 28428 KB Output is correct
28 Correct 55 ms 12940 KB Output is correct
29 Correct 3052 ms 28080 KB Output is correct
30 Correct 2902 ms 28164 KB Output is correct
31 Correct 1950 ms 26676 KB Output is correct
32 Correct 2105 ms 26812 KB Output is correct
33 Correct 8754 ms 49840 KB Output is correct
34 Correct 8803 ms 49800 KB Output is correct
35 Correct 7853 ms 50036 KB Output is correct
36 Correct 5029 ms 50124 KB Output is correct
37 Correct 5106 ms 49964 KB Output is correct
38 Correct 5233 ms 50596 KB Output is correct