Submission #1157845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157845		adiyer	Road Construction (JOI21_road_construction)	C++20	0 / 100	10095 ms	127632 KiB

road_construction

#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")

#include <ext/pb_ds/assoc_container.hpp>     
#include <ext/pb_ds/tree_policy.hpp>  
#include <bits/stdc++.h>

#define ordered_set tree < pair < ll, ll >, null_type, less < pair < ll, ll > >, rb_tree_tag, tree_order_statistics_node_update > 
#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first 
#define S second 

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double ld;

const int N = 2.5e5 + 11;
const int MAX = 2e4 + 11;
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, k, lst, sz;
ll x[N], y[N];

vector < pair < pair < ll, ll >, bool > > v;

map < pair < ll, ll >, ll > mp;

vector < ll > ans;

ordered_set st;

pair < ll, ll > flip(pair < ll, ll > x){
  return {x.F + x.S, x.F - x.S};
}

ll f(ll d){
  ll sum = 0;
  st.clear(), mp.clear(), v.clear(), sz = 0;
  for(ll i = 1; i <= n; i++){
    pair < ll, ll > it = {x[i] + y[i], x[i] - y[i]};
    pair < ll, ll > it1 = {x[i] + y[i] + d, x[i] - y[i] + d};
    pair < ll, ll > it2 = {x[i] + y[i] - d - 1, x[i] - y[i] - d - 1};
    pair < ll, ll > it3 = {x[i] + y[i] + d, x[i] - y[i] - d - 1};
    pair < ll, ll > it4 = {x[i] + y[i] - d - 1, x[i] - y[i] + d};
    v.pb({it, 1});
    v.pb({it1, 0});
    v.pb({it2, 0});
    v.pb({it3, 0});
    v.pb({it4, 0});
  }
  sort(all(v));
  for(ll i = 0; i < len(v); i++){
    ll j = i;
    while(i + 1 < len(v) && v[i].F.F == v[i + 1].F.F){
      if(v[i].S) st.insert({v[i].F.S, ++sz}); 
      i++;
    }
    if(v[i].S) st.insert({v[i].F.S, ++sz});
    while(j <= i) mp[v[j].F] = st.order_of_key({v[j].F.S + 1, -inf}), j++;
  }
  for(ll i = 1; i <= n; i++){
    pair < ll, ll > it = {x[i] + y[i], x[i] - y[i]};
    pair < ll, ll > it1 = {x[i] + y[i] + d, x[i] - y[i] + d};
    pair < ll, ll > it2 = {x[i] + y[i] - d - 1, x[i] - y[i] - d - 1};
    pair < ll, ll > it3 = {x[i] + y[i] + d, x[i] - y[i] - d - 1};
    pair < ll, ll > it4 = {x[i] + y[i] - d - 1, x[i] - y[i] + d};
    ll cur = mp[it1] + mp[it2] - mp[it3] - mp[it4];
    sum += cur - 1;
  }
  return sum / 2;
}

void solve(){
  cin >> n >> k;
  for(ll i = 1; i <= n; i++) cin >> x[i] >> y[i];
  while(1){
    ll l = 0, r = 2e9 + 1;
    while(r - l > 1){
      ll md = (l + r) / 2;
      if(f(md) > lst) r = md;
      else l = md;
    }
    ll cnt = f(r);
    for(ll i = 0; i < cnt - lst; i++){ 
      ans.pb(r);
      if(len(ans) == k){
        for(ll val : ans) cout << val << '\n';
        exit(0);
      }
    }
    lst = cnt;
  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tt = 1;
  // cin >> tt;
  while(tt--) solve();
}

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