Submission #386396

#	Time	Username	Problem	Language	Result	Execution time	Memory
386396		MatheusLealV	Road Construction (JOI21_road_construction)	C++17	100 / 100	4187 ms	693832 KiB

road_construction

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
#define N 250020
int n, k;
pii w[N];
int bit[N],ans[N];
inline void upd(int x, int v){
	x+=4;
	assert(x>0);
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}
inline int qry(int x){
	x+=4;
	assert(x>0);
	int sum = 0;
	for(int i = x;i>0;i-=(i&-i)) sum+=bit[i];
	return sum;
}
vector<ll> compress;
int compy[N], pilhax[N], pilhay[N], pilhaid[N];
deque<int>tree[4*N];
#define m ((a+b)/2)
void updd(int nod, int a, int b, int i, int j,bool add){
	if(add) tree[nod].pb(j);
	else tree[nod].pop_front();
	if(a==b) return;
	if(i <= m) updd(2*nod,a,m,i,j,add);
	else updd(2*nod+1,m+1,b,i,j,add);
}
void get(int nod, int a, int b, int i, int j, vector<int>&curr){
	if(j < a or i > b) return;
	if(i <= a and j >= b){
		for(auto x: tree[nod]){
			curr.pb(x);
		}
		return;
	}
	get(2*nod, a, m, i, j, curr);get(2*nod+1,m+1,b,i,j,curr);
}
inline int check(int mid){
	for(int i = 0; i <= n+10;i++) bit[i]=0;
	int l=0,r=-1, cost=0;
	for(int i=1;i<=n;i++){
		int mn = 1+(lower_bound(compress.begin(), compress.end(), w[i].s-mid)-compress.begin());
		int mx = (upper_bound(compress.begin(), compress.end(), w[i].s+mid)-compress.begin());
		while(l <= r and pilhax[l] < w[i].f-mid){
			upd(pilhay[l], -1);
			l++;
		}
		if(mn <= mx) cost+=qry(mx)-qry(mn-1);
		if(cost>=k)return cost;
		r++;
		pilhax[r] = w[i].f;//({w[i].f, compy[i]});
		pilhay[r] = compy[i];
		upd(compy[i], 1);
	}
	return cost;
}

inline void take(int mid, vector<int>&ans){
	int l=0,r=-1, cost=0;
	for(int i=1;i<=n;i++){
		while(l <= r and pilhax[l] < w[i].f-mid){
			updd(1,1,n,pilhay[l], pilhaid[l], 0);
			l++;
		}
		int mn = 1+(lower_bound(compress.begin(), compress.end(), w[i].s-mid)-compress.begin());
		int mx = (upper_bound(compress.begin(), compress.end(), w[i].s+mid)-compress.begin());
		vector<int>curr;
		get(1,1,n,mn,mx, curr);
		for(auto x: curr){
			int dx = abs(w[i].f - w[x].f), dy = abs(w[i].s - w[x].s);
			ans.pb(max(dx,dy));
		}
		r++;
		pilhax[r] = w[i].f;//({w[i].f, compy[i]});
		pilhay[r] = compy[i];
		pilhaid[r] = i;
		updd(1,1,n,pilhay[r], pilhaid[r], 1);
	}
}
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int i = 1, x, y; i <= n; i++){
		cin>>x>>y;
		w[i]={x+y,x-y};
		compress.push_back(x-y);
	}
	sort(w+1,w+n+1);
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(),compress.end()),compress.end());
	for(int i = 1; i<=n;i++)compy[i] = (upper_bound(compress.begin(), compress.end(), w[i].s)-compress.begin());
	int ini = 0, fim = (int)(4e9), mid, best=-1;
	while(fim>=ini){
		mid=(ini+fim)/2;
		if(check(mid) >= k) best=mid,fim=mid-1;
		else ini=mid+1;
	}
	vector<int> ans;
	int S = check(best - 1);
	for(int i = 0; i < k-S; i++) ans.pb(best);

	take(best-1,ans);

	sort(all(ans));
	for(int i=0;i<sz(ans);i++)cout<<ans[i]<<"\n";
}

Compilation message (stderr)

road_construction.cpp: In function 'void take(long long int, std::vector<long long int>&)':
road_construction.cpp:77:16: warning: unused variable 'cost' [-Wunused-variable]
   77 |  int l=0,r=-1, cost=0;
      |                ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35