제출 #894473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894473		pcc	Road Construction (JOI21_road_construction)	C++14	100 / 100	7075 ms	101484 KiB

road_construction

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35