Submission #1145808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145808		fryingduc	Road Construction (JOI21_road_construction)	C++20	7 / 100	3839 ms	2102880 KiB

road_construction

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 250005;
int n, k;
long long x[maxn], y[maxn]; 
int vx[maxn], vy[maxn];
vector<long long> vec;
int ord[maxn];

int bit[maxn];
void update(int i, int val) {
  for(; i <= n; i += i & (-i)) {
    bit[i] += val;
  }
}

int get(int i) {
  int ans = 0;
  for(; i > 0; i -= i & (-i)) {
    ans += bit[i];
  }
  return ans;
}

bool check(long long mid) {
  long long res = 0;
  memset(bit, 0, sizeof(bit));
  int ptr = 1;
  for(int i = 1; i <= n; ++i) {
    while(ptr < i and x[ord[i]] - x[ord[ptr]] > mid) {
      update(vy[ord[ptr]], -1);
      ++ptr;
    }
    int p1 = upper_bound(vec.begin(), vec.end(), y[ord[i]] + mid) - vec.begin();
    int p2 = lower_bound(vec.begin(), vec.end(), y[ord[i]] - mid) - vec.begin();
    res += get(p1) - get(p2);
    update(vy[ord[i]], 1);
  }
  return res >= k;
}

void solve() {
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    int a, b; cin >> a >> b;
    x[i] = a + b, y[i] = a - b;
    vec.push_back(y[i]);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for(int i = 1; i <= n; ++i) {
    vy[i] = lower_bound(vec.begin(), vec.end(), y[i]) - vec.begin() + 1;
  }
  iota(ord + 1, ord + n + 1, 1);
  sort(ord + 1, ord + n + 1, [](const int &a, const int &b) -> bool {
    return x[a] < x[b];
  });
  long long l = 0, r = 4e9, res = 4e9;
  while(l <= r) {
    long long mid = (l + r) >> 1;
    if(check(mid)) {
      res = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  int ptr = 1;
  set<pair<int, int>> s;
  vector<long long> cand;
  for(int i = 1; i <= n; ++i) {
    while(ptr < i and x[ord[i]] - x[ord[ptr]] >= res) {
      s.erase(s.find(make_pair(y[ord[ptr]], ord[ptr])));
      ++ptr;
    }
    auto t1 = s.upper_bound(make_pair(y[ord[i]] + res - 1, n + 1));
    auto t = s.lower_bound(make_pair(y[ord[i]] - res + 1, -1));
    while(t != t1) {
      int id = t->second;
      cand.push_back(max(abs(x[ord[i]] - x[id]), abs(y[ord[i]] - y[id])));
      t++;
    }
    s.insert(make_pair(y[ord[i]], ord[i]));
  }
  sort(cand.begin(), cand.end());
  debug(cand);
  while((int)cand.size() < k) {
    cand.push_back(res);
  }
  for(auto i:cand) {
    cout << i << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
5 10
1 -1
2 0
-1 0
0 2
0 -2
*/

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