Submission #386471

#	Time	Username	Problem	Language	Result	Execution time	Memory
386471		VROOM_VARUN	Road Construction (JOI21_road_construction)	C++14	100 / 100	4313 ms	28036 KiB

road_construction

/*
ID: varunra2
LANG: C++
TASK: road
*/

// we precalculate sqrt(n) smallest values of each point
// it is your value if it is to your left

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define int long long

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

struct bit {
  int n;
  VI bit;
  void init(int _n) {
    n = _n;
    bit.assign(n + 1, 0);
  }

  void upd(int ind, int val) {
    // debug("in");
    // debug(ind);
    ind++;
    while (ind <= n) {
      bit[ind] += val;
      ind += (ind & (-ind));
    }
    // debug("out");
  }

  int qry(int ind) {
    int ret = 0;
    // debug("indd");
    ind++;
    while (ind >= 1) {
      ret += bit[ind];
      ind -= (ind & (-ind));
    }
    // debug("outt");
    return ret;
  }

  int qry(int l, int r) { return qry(r) - qry(l - 1); }
} fen;

int n, k;
VII vals;
MPII cmp;
VI pnts;

void init() { vals.resize(n); }

void transform() {
  // convert all the points into chebyshev distance
  for (int i = 0; i < n; i++) {
    int x, y;
    tie(x, y) = vals[i];
    vals[i].x = x + y;
    vals[i].y = x - y;
  }
}

void comp() {
  for (int i = 0; i < n; i++) {
    pnts.PB(vals[i].y);
  }
  sort(all(pnts));
  pnts.erase(unique(all(pnts)), pnts.end());
  rep(i, 0, sz(pnts)) cmp[pnts[i]] = i;
}

bool count(int dist) {
  fen.init(sz(pnts) + 2);
  // VVI evnts;
  // for (int i = 0; i < n; i++) {
  // evnts.PB({vals[i].x, 0, i});
  // evnts.PB({vals[i].x + dist, 1, i});
  // }
  // sort(all(evnts));
  int p2 = 0;
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    // remove points
    while (vals[i].x - vals[p2].x > dist) {
      int pt = lower_bound(all(pnts), vals[p2].y) - pnts.begin();
      fen.upd(pt, -1);
      p2++;
    }
    // add contribution
    int l = lower_bound(all(pnts), vals[i].y - dist) - pnts.begin();
    auto p1 = upper_bound(all(pnts), vals[i].y + dist);
    if (p1 != pnts.begin()) {
      p1--;
      int r = p1 - pnts.begin();
      if (l <= r) {
        cnt += fen.qry(l, r);
        if (cnt >= k) return false;
      }
    }
    // add new point
    int pt = lower_bound(all(pnts), vals[i].y) - pnts.begin();
    fen.upd(pt, 1);
  }
  return true;
}

int dst(int i, int j) {
  return max(abs(vals[i].x - vals[j].x), abs(vals[i].y - vals[j].y));
}

VI gen(int dist) {
  VI ret;
  set<PII> st;
  // VVI evnts;
  // for (int i = 0; i < n; i++) {
  //   evnts.PB({vals[i].x, 0, i});
  //   evnts.PB({vals[i].x + dist, 1, i});
  // }
  // sort(all(evnts));
  int p2 = 0;
  for (int i = 0; i < n; i++) {
    while (vals[i].x - vals[p2].x > dist) {
      st.erase(MP(vals[p2].y, p2));
      p2++;
    }
    auto it = st.lower_bound(MP(vals[i].y - dist, -1));
    while (it != st.end()) {
      if ((*it).x > vals[i].y + dist) break;
      ret.PB(dst(i, (*it).y));
      it++;
    }
    st.insert(MP(vals[i].y, i));
  }
  return ret;
}

int32_t main() {
  // #ifndef ONLINE_JUDGE
  // freopen("meetings2.in", "r", stdin);
  // freopen("meetings2.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;

  init();

  trav(x, vals) cin >> x.x >> x.y;

  transform();
  sort(all(vals));

  comp();

  // int x = -1;

  // for (int b = (int)4e9; b >= 1; b /= 2) {
  //   while (count(x + b)) x += b;
  // }
  // auto ret = gen(x);

  int s = 0, e = 4e9;
  while (s != e) {
    int m = (s + e + 1) / 2;
    if (count(m))
      s = m;
    else
      e = m - 1;
  }

  if (k == 1) {
    cout << s + 1 << '\n';
    exit(0);
  }

  VI ret = gen(s);

  while (sz(ret) < k) ret.PB(s + 1);

  sort(all(ret));

  trav(x, ret) cout << x << '\n';

  debug(s + 1);

  return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 42
      |                    ^~
road_construction.cpp:233:3: note: in expansion of macro 'debug'
  233 |   debug(s + 1);
      |   ^~~~~

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