oj.uz

Submission #894471

# Submission time Handle Problem Language Result Execution time Memory
894471 2023-12-28T10:37:32 Z pcc Road Construction (JOI21_road_construction) C++14
100 / 100
 6755 ms 106704 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll

const ll inf = 1e10;
const int mxn = 250005;
int N,K;
ll bit[mxn*2];
pll arr[mxn];
vector<ll> all;
vector<int> ans;

struct Q{
	int tp;
	ll l,r;
	ll x,id;
	Q(){}
	Q(ll tt,ll xx,ll s,ll e,ll ii = 0){
		tp = tt,x = xx,l = s,r = e;
		id = ii;
	}
	bool operator<(Q &b)const{
		return x == b.x?tp<b.tp:x<b.x;
	}
};

vector<Q> op;
void modify(int p,ll v){
	for(;p<mxn*2;p+=p&-p)bit[p] += v;
	return;
}
ll getval(ll p){
	ll re = 0;
	for(;p>0;p-= p&-p)re += bit[p];
	return re;
}

inline ll calc(ll len){
	memset(bit,0,sizeof(bit));
	op.clear();
	for(int i = 1;i<=N;i++){
		ll tl = arr[i].sc-len,tr = arr[i].sc+len;
		tl = lower_bound(all.begin(),all.end(),tl)-all.begin();
		tr = upper_bound(all.begin(),all.end(),tr)-all.begin();
		ll tmp = lower_bound(all.begin(),all.end(),arr[i].sc)-all.begin();
		op.push_back(Q(0,arr[i].fs-len,tl,tr));
		op.push_back(Q(-1,arr[i].fs+len+1,tl,tr));
		op.push_back(Q(1,arr[i].fs,tmp,tmp));
	}
	ll re = 0;
	sort(op.begin(),op.end());
	for(auto &i:op){
		if(i.tp == 0){
			modify(i.l,1);
			modify(i.r,-1);
		}
		else if(i.tp == -1){
			modify(i.l,-1);
			modify(i.r,1);
		}
		else{
			re += getval(i.l);
		}
	}
	assert((re-N)%2 == 0);
	return (re-N)/2;
}

set<int> segtree[mxn*4];

void addval(int now,int l,int r,int s,int e,int v){
	if(l>=s&&e>=r){
		if(v>0)segtree[now].insert(v);
		else segtree[now].erase(-v);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)addval(now*2+1,l,mid,s,e,v);
	if(mid<e)addval(now*2+2,mid+1,r,s,e,v);
	return;
}

void getp(int now,int l,int r,int p,int id){
	for(auto &i:segtree[now]){
		if(id>=i)continue;
		ans.push_back(max(abs(arr[id].fs-arr[i].fs),abs(arr[id].sc-arr[i].sc)));
	}
	if(l == r)return;
	int mid = (l+r)>>1;
	if(mid>=p)getp(now*2+1,l,mid,p,id);
	else getp(now*2+2,mid+1,r,p,id);
	return;
}

void getans(int len){
	op.clear();
	for(int i = 1;i<=N;i++){
		ll tl = arr[i].sc-len,tr = arr[i].sc+len;
		tl = lower_bound(all.begin(),all.end(),tl)-all.begin();
		tr = upper_bound(all.begin(),all.end(),tr)-all.begin();
		ll tmp = lower_bound(all.begin(),all.end(),arr[i].sc)-all.begin();
		op.push_back(Q(0,arr[i].fs-len,tl,tr,i));
		op.push_back(Q(-1,arr[i].fs+len+1,tl,tr,i));
		op.push_back(Q(1,arr[i].fs,tmp,tmp,i));
	}
	sort(op.begin(),op.end());
	for(auto &i:op){
		if(i.tp == 0)addval(0,0,all.size(),i.l,i.r-1,i.id);
		else if(i.tp == -1)addval(0,0,all.size(),i.l,i.r-1,-i.id);
		else getp(0,0,all.size(),i.l,i.id);
	}
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc;
		arr[i] = make_pair(arr[i].fs+arr[i].sc,-arr[i].fs+arr[i].sc);
		all.push_back(arr[i].sc);
	}
	//for(int i =1;i<=N;i++)cout<<arr[i].fs<<','<<arr[i].sc<<' ';cout<<endl;
	all.push_back(-inf);
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	ll l = 1,r = 4e9;
	while(l != r){
		ll mid = (l+r)>>1;
		if(calc(mid)>=K)r = mid;
		else l = mid+1;
	}
	//cout<<"MAX:"<<l<<' '<<calc(l)<<endl;
	getans(l-1);
	//for(auto &i:ans)cout<<i<<',';cout<<endl;
	while(ans.size()<K)ans.push_back(l);
	sort(ans.begin(),ans.end());
	for(auto &i:ans)cout<<i<<'\n';
	return 0;
}

Compilation message

road_construction.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  122 | main(){
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:143:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  143 |  while(ans.size()<K)ans.push_back(l);
      |        ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 58280 KB Output is correct
2 Correct 67 ms 58236 KB Output is correct
3 Correct 60 ms 58544 KB Output is correct
4 Correct 60 ms 58540 KB Output is correct
5 Correct 61 ms 57256 KB Output is correct
6 Correct 25 ms 53340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5749 ms 103280 KB Output is correct
2 Correct 5784 ms 103884 KB Output is correct
3 Correct 59 ms 58444 KB Output is correct
4 Correct 5632 ms 103336 KB Output is correct
5 Correct 5602 ms 103084 KB Output is correct
6 Correct 5646 ms 103580 KB Output is correct
7 Correct 5603 ms 103212 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6097 ms 106416 KB Output is correct
2 Correct 6101 ms 106588 KB Output is correct
3 Correct 12 ms 53200 KB Output is correct
4 Correct 5559 ms 104368 KB Output is correct
5 Correct 4000 ms 105908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6097 ms 106416 KB Output is correct
2 Correct 6101 ms 106588 KB Output is correct
3 Correct 12 ms 53200 KB Output is correct
4 Correct 5559 ms 104368 KB Output is correct
5 Correct 4000 ms 105908 KB Output is correct
6 Correct 6158 ms 105796 KB Output is correct
7 Correct 6020 ms 105132 KB Output is correct
8 Correct 13 ms 53084 KB Output is correct
9 Correct 12 ms 52932 KB Output is correct
10 Correct 6117 ms 106152 KB Output is correct
11 Correct 5559 ms 104120 KB Output is correct
12 Correct 3974 ms 105656 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 58280 KB Output is correct
2 Correct 67 ms 58236 KB Output is correct
3 Correct 60 ms 58544 KB Output is correct
4 Correct 60 ms 58540 KB Output is correct
5 Correct 61 ms 57256 KB Output is correct
6 Correct 25 ms 53340 KB Output is correct
7 Correct 2445 ms 80188 KB Output is correct
8 Correct 2418 ms 80696 KB Output is correct
9 Correct 61 ms 58540 KB Output is correct
10 Correct 2223 ms 80704 KB Output is correct
11 Correct 2136 ms 80604 KB Output is correct
12 Correct 1542 ms 81212 KB Output is correct
13 Correct 1551 ms 80952 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 58280 KB Output is correct
2 Correct 67 ms 58236 KB Output is correct
3 Correct 60 ms 58544 KB Output is correct
4 Correct 60 ms 58540 KB Output is correct
5 Correct 61 ms 57256 KB Output is correct
6 Correct 25 ms 53340 KB Output is correct
7 Correct 5749 ms 103280 KB Output is correct
8 Correct 5784 ms 103884 KB Output is correct
9 Correct 59 ms 58444 KB Output is correct
10 Correct 5632 ms 103336 KB Output is correct
11 Correct 5602 ms 103084 KB Output is correct
12 Correct 5646 ms 103580 KB Output is correct
13 Correct 5603 ms 103212 KB Output is correct
14 Correct 6097 ms 106416 KB Output is correct
15 Correct 6101 ms 106588 KB Output is correct
16 Correct 12 ms 53200 KB Output is correct
17 Correct 5559 ms 104368 KB Output is correct
18 Correct 4000 ms 105908 KB Output is correct
19 Correct 6158 ms 105796 KB Output is correct
20 Correct 6020 ms 105132 KB Output is correct
21 Correct 13 ms 53084 KB Output is correct
22 Correct 12 ms 52932 KB Output is correct
23 Correct 6117 ms 106152 KB Output is correct
24 Correct 5559 ms 104120 KB Output is correct
25 Correct 3974 ms 105656 KB Output is correct
26 Correct 2445 ms 80188 KB Output is correct
27 Correct 2418 ms 80696 KB Output is correct
28 Correct 61 ms 58540 KB Output is correct
29 Correct 2223 ms 80704 KB Output is correct
30 Correct 2136 ms 80604 KB Output is correct
31 Correct 1542 ms 81212 KB Output is correct
32 Correct 1551 ms 80952 KB Output is correct
33 Correct 6755 ms 105436 KB Output is correct
34 Correct 6642 ms 105520 KB Output is correct
35 Correct 6123 ms 105032 KB Output is correct
36 Correct 4017 ms 106704 KB Output is correct
37 Correct 4035 ms 105912 KB Output is correct
38 Correct 4011 ms 106240 KB Output is correct