Submission #386365

#	Time	Username	Problem	Language	Result	Execution time	Memory
386365		Mamnoon_Siam	Road Construction (JOI21_road_construction)	C++17	100 / 100	5973 ms	18344 KiB

road_construction

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
#define x first
#define y second
typedef pair<ll, ll> pt;

const int N = 250005;

int n, k;
pt a[N];
vi byX;
ll Ys[N]; int Ysz;
int lessY(ll y) {
  return int(lower_bound(Ys, Ys+Ysz, y) - Ys);
}
int ft[N];
void update(int pos, int val) {
  for(; pos < N; pos += pos & -pos) ft[pos] += val;
}
int query(int l, int r, int ret = 0) {
  for(l--; l > 0; l -= l & -l) ret -= ft[l];
  for(; r > 0; r -= r & -r) ret += ft[r];
  return ret;
}

ll count(ll d) {
  memset(ft, 0, sizeof ft);
  ll pairs = 0;
  int ptr = 1;
  for(int i = 1; i <= n; ++i) {
    while(a[ptr].x < a[i].x - d) {
      int j = lessY(a[ptr++].y) + 1;
      update(j, -1);
    }
    {
      int l = lessY(a[i].y - d) + 1;
      int r = lessY(a[i].y + d + 1);
      int me = lessY(a[i].y) + 1;
      pairs += query(l, r);
      update(me, +1);
    }
  }
  return pairs;
}

vector<ii> Less(ll d) {
  using pli = pair<ll, int>;
  set<pli> st;
  vector<ii> ret;
  int ptr = 1;
  for(int i = 1; i <= n; ++i) {
    while(a[ptr].x <= a[i].x - d) {
      st.erase(pli(a[ptr].y, ptr));
      ptr++;
    }
    auto lit = st.upper_bound(pli(a[i].y-d, INT_MAX));
    auto rit = st.lower_bound(pli(a[i].y+d, INT_MIN));
    for(auto it = lit; it != rit; ++it) {
      ret.emplace_back(i, it -> se);
    }
    st.insert(pli(a[i].y, i));
  }
  return ret;
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d", &n, &k);
  // assert(n <= 1000);
  // assert(k == 1);
  for(int i = 1; i <= n; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    a[i].x = x + y;
    a[i].y = x - y;
    Ys[i-1] = a[i].y;
  }
  sort(a+1, a+1+n);
  sort(Ys, Ys+n);
  Ysz = int(unique(Ys, Ys+n) - Ys);

  ll lo = 1, hi = 4000000000LL, low = -1;
  while(lo <= hi) {
    ll mid = (lo + hi) >> 1;
    if(count(mid) >= k) {
      low = mid;
      hi = mid-1;
    } else {
      lo = mid+1;
    }
  }
  auto les = Less(low);

  vector<ll> ans;
  for(auto [i, j] : les) {
    ans.emplace_back(max(abs(a[i].x - a[j].x), abs(a[i].y - a[j].y)));
  }
  for(int i = 0; i < k-sz(les); ++i) ans.emplace_back(low);
  sort(all(ans));

  for(ll x : ans) printf("%lld\n", x);
  return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main(int, const char**)':
road_construction.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d %d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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