Submission #1253774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253774		LucaLucaM	Road Construction (JOI21_road_construction)	C++20	6 / 100	8179 ms	127020 KiB

road_construction

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

#define int ll

// acum sper ca zboara :pray:

using ll = long long;

#define debug(x) #x << " = " << x << '\n'

const ll INF = 1e18;
const int MAXN = 250'000;

struct Point {
  ll x, y;
};

struct Event {
  ll x;
  ll l, r;
  int sign;
  Event() {}
  Event(ll a, ll b, ll c, int d) : x(a), l(b), r(c), sign(d) {}
  bool operator < (const Event &other) const {
    return x != other.x? x < other.x : std::abs(sign) < std::abs(other.sign);
  };
};

struct Fenwick {
  std::vector<int> aib;
  int n;
  void init(int _n) {
    n = _n + 1;
    aib.assign(n, 0);
  }

  void update(int p, int v) {
    for (; p < n; p += p & -p) {
      aib[p] += v;
    }
  }
  int query(int p) {
    int ret = 0;
    for (; p > 0; p -= p & -p) {
      ret += aib[p];
    }
    return ret;
  }
};

std::set<int> aint[4 * MAXN + 15]; // trust the process
std::set<std::pair<int, int>> have;

void update(int node, int tl, int tr, int l, int r, int id, int type) {
  if (l <= tl && tr <= r)  {
    if  (type == +1) {
      aint[node].insert(id);
    } else {
      aint[node].erase(id);
    }
  } else {
    int mid = (tl + tr) / 2;
    if (l <= mid) {
      update(2 * node, tl, mid, l, r, id, type);
    }
    if (mid < r) {
      update(2 * node + 1, mid + 1, tr, l, r, id, type);
    }
  }
}

void collect(int node, int tl, int tr, int q, int id) {
  for (int p : aint[node]) {
    if (p < id) {
      have.insert({p, id});
    } else if (id < p) {
      have.insert({id, p});
    }
  }

  if (tl == tr) {
    return;
  }

  int mid = (tl + tr) / 2;
  if (q <= mid) {
    collect(2 * node, tl, mid, q, id);
  } else { 
    collect(2 * node + 1, mid + 1, tr, q, id);
  }
}

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

  int n, k;
  std::cin >> n >> k;

  std::vector<Point> a(n);
  std::vector<Point> og(n);

  for (int i = 0; i < n; i++) {
    int x, y;
    std::cin >> x >> y;
    og[i] = {x, y};
    a[i] = {x - y, x + y};
  }
  
  Fenwick aib;
  aib.init(3 * n + 1);

  auto countPairs = [&](int d) {
    std::vector<Event> events;
    std::vector<ll> norm;
    for (int i = 0; i < n; i++) {
      events.push_back({a[i].x + d, a[i].y - d, a[i].y + d, +1});
      events.push_back({a[i].x - d - 1, a[i].y - d, a[i].y + d, -1});
      events.push_back({a[i].x, a[i].y, 0, 0});
      norm.push_back({a[i].y});
    }
    norm.push_back(-INF);
    std::sort(norm.begin(), norm.end());
    norm.erase(std::unique(norm.begin(), norm.end()), norm.end());
    
    std::sort(events.begin(), events.end());

    ll ret = 0;
    aib.init(n + 1);

    for (auto [x, l, r, t] : events) {
      l = std::lower_bound(norm.begin(), norm.end(), l) - norm.begin();
      r = std::lower_bound(norm.begin(), norm.end(), r) - norm.begin();
      if (t == 0) {
        aib.update(l, +1);
      } else {
        ret += (aib.query(r) - aib.query(l - 1)) * t;
      }
    }

    norm.clear();
    events.clear();

    ret -= n;
    
    return ret / 2;
  };

  ll l = 0, r = 4e9;
  while (l < r) {
    ll mid = (l + r) / 2;
    if (countPairs(mid) >= k) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  // ok cred ca era mult mai penal daca doar normalizam si faceam un pst dar oh well hai sa incerc sa bag asta

  ll d = r;

  std::vector<Event> events;
  std::vector<ll> norm;
  norm.push_back(-INF);
  for (int i = 0; i < n; i++) {
    events.push_back({a[i].x - d, a[i].y - d, a[i].y + d, +(i + 1)});
    events.push_back({a[i].x + d + 1, a[i].y - d, a[i].y + d, -(i + 1)});
    events.push_back({a[i].x, a[i].y, i + 1, 0});
    norm.push_back(a[i].y);
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());

  std::sort(events.begin(), events.end());
  
  for (auto [x, l, r, t] : events) {
    l = std::lower_bound(norm.begin(), norm.end(), l) - norm.begin();
    int i;
    if (t) {
      i = std::abs(t) - 1;
      t /= std::abs(t);
      r = std::lower_bound(norm.begin(), norm.end(), r) - norm.begin();
    } else {
      i = r - 1;
    }
    if (t == 0) {
      int p = std::lower_bound(norm.begin(), norm.end(), a[i].y) - norm.begin();
      collect(1, 1, n, p, i);
    } else {
      update(1, 1, n, l, r, i, t);
    }
  }
  
  std::vector<ll> answer;
  for (const auto &[x, y] : have) {
    answer.push_back(std::abs(og[x].x - og[y].x) + std::abs(og[x].y - og[y].y));
  }
  std::sort(answer.begin(), answer.end());
  answer.resize(k);
  for (auto x : answer) {
    std::cout << x << ' ';
  }

  return 0;
}

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