oj.uz

Submission #894473

# Submission time Handle Problem Language Result Execution time Memory
894473 2023-12-28T10:41:10 Z pcc Road Construction (JOI21_road_construction) C++14
100 / 100
 7075 ms 101484 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3,unroll-loops")

#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>

const ll inf = 1e10;
const int mxn = 250005;
int N,K;
ll bit[mxn*2];
pll arr[mxn];
vector<ll> all;
vector<ll> 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(ll 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:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main(){
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:144:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |  while(ans.size()<K)ans.push_back(l);
      |        ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 58272 KB Output is correct
2 Correct 72 ms 58324 KB Output is correct
3 Correct 61 ms 58512 KB Output is correct
4 Correct 60 ms 58680 KB Output is correct
5 Correct 63 ms 57252 KB Output is correct
6 Correct 27 ms 53340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6232 ms 99760 KB Output is correct
2 Correct 6286 ms 100332 KB Output is correct
3 Correct 64 ms 58240 KB Output is correct
4 Correct 6092 ms 101484 KB Output is correct
5 Correct 6143 ms 100524 KB Output is correct
6 Correct 6202 ms 100220 KB Output is correct
7 Correct 6107 ms 99760 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6513 ms 99980 KB Output is correct
2 Correct 6567 ms 99800 KB Output is correct
3 Correct 12 ms 53080 KB Output is correct
4 Correct 6047 ms 100792 KB Output is correct
5 Correct 4461 ms 99484 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6513 ms 99980 KB Output is correct
2 Correct 6567 ms 99800 KB Output is correct
3 Correct 12 ms 53080 KB Output is correct
4 Correct 6047 ms 100792 KB Output is correct
5 Correct 4461 ms 99484 KB Output is correct
6 Correct 6508 ms 100264 KB Output is correct
7 Correct 6569 ms 100304 KB Output is correct
8 Correct 12 ms 53084 KB Output is correct
9 Correct 12 ms 53164 KB Output is correct
10 Correct 6544 ms 100964 KB Output is correct
11 Correct 6006 ms 100268 KB Output is correct
12 Correct 4330 ms 101300 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 58272 KB Output is correct
2 Correct 72 ms 58324 KB Output is correct
3 Correct 61 ms 58512 KB Output is correct
4 Correct 60 ms 58680 KB Output is correct
5 Correct 63 ms 57252 KB Output is correct
6 Correct 27 ms 53340 KB Output is correct
7 Correct 2599 ms 78656 KB Output is correct
8 Correct 2623 ms 78192 KB Output is correct
9 Correct 63 ms 58540 KB Output is correct
10 Correct 2390 ms 77496 KB Output is correct
11 Correct 2328 ms 77756 KB Output is correct
12 Correct 1728 ms 77368 KB Output is correct
13 Correct 1742 ms 78140 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 58272 KB Output is correct
2 Correct 72 ms 58324 KB Output is correct
3 Correct 61 ms 58512 KB Output is correct
4 Correct 60 ms 58680 KB Output is correct
5 Correct 63 ms 57252 KB Output is correct
6 Correct 27 ms 53340 KB Output is correct
7 Correct 6232 ms 99760 KB Output is correct
8 Correct 6286 ms 100332 KB Output is correct
9 Correct 64 ms 58240 KB Output is correct
10 Correct 6092 ms 101484 KB Output is correct
11 Correct 6143 ms 100524 KB Output is correct
12 Correct 6202 ms 100220 KB Output is correct
13 Correct 6107 ms 99760 KB Output is correct
14 Correct 6513 ms 99980 KB Output is correct
15 Correct 6567 ms 99800 KB Output is correct
16 Correct 12 ms 53080 KB Output is correct
17 Correct 6047 ms 100792 KB Output is correct
18 Correct 4461 ms 99484 KB Output is correct
19 Correct 6508 ms 100264 KB Output is correct
20 Correct 6569 ms 100304 KB Output is correct
21 Correct 12 ms 53084 KB Output is correct
22 Correct 12 ms 53164 KB Output is correct
23 Correct 6544 ms 100964 KB Output is correct
24 Correct 6006 ms 100268 KB Output is correct
25 Correct 4330 ms 101300 KB Output is correct
26 Correct 2599 ms 78656 KB Output is correct
27 Correct 2623 ms 78192 KB Output is correct
28 Correct 63 ms 58540 KB Output is correct
29 Correct 2390 ms 77496 KB Output is correct
30 Correct 2328 ms 77756 KB Output is correct
31 Correct 1728 ms 77368 KB Output is correct
32 Correct 1742 ms 78140 KB Output is correct
33 Correct 7075 ms 100412 KB Output is correct
34 Correct 7072 ms 100660 KB Output is correct
35 Correct 6563 ms 100056 KB Output is correct
36 Correct 4475 ms 100276 KB Output is correct
37 Correct 4531 ms 99604 KB Output is correct
38 Correct 4464 ms 100316 KB Output is correct