제출 #554793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554793		MilosMilutinovic	Road Construction (JOI21_road_construction)	C++14	6 / 100	10008 ms	149400 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  auto Count = [&](long long d) {
    vector<tuple<long long, int, long long, long long>> ev;
    vector<long long> xs;
    for (int i = 0; i < n; i++) {
      long long dx = x[i] + y[i];
      long long dy = x[i] - y[i];
      ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
      ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
      ev.emplace_back(dx, 2, dy, dy);
      xs.push_back(dy - d - 1);
      xs.push_back(dy + d);
      xs.push_back(dy);
    }
    sort(ev.begin(), ev.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int sz = xs.size();
    fenwick<int> fenw(sz);
    long long cnt = 0;
    for (auto& e : ev) {
      int t = get<1>(e);
      if (t == 0) {
        int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
        int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
        cnt -= fenw.get(R) - fenw.get(L);
      } else if (t == 1) {
        int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
        int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
        cnt += fenw.get(R) - fenw.get(L);
      } else {
        int aa = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
        fenw.modify(aa, +1);
      }
    }
    return (cnt - n) / 2;
  };
  long long low = 0, high = 4.1e9;
  while (low + 1 < high) {
    long long mid = (low + high + 1) >> 1;
    if (Count(mid) >= k) {
      high = mid;
    } else {
      low = mid;
    }
  }
  vector<long long> ans;
  vector<vector<int>> ids(12 * n);
  function<void(int, int, int, int, int)> add = [&](int node, int l, int r, int i, int id) {
    ids[node].push_back(id);
    if (l == r) {
      return;
    }
    int mid = l + r >> 1;
    if (i <= mid) {
      add(node + node, l, mid, i, id);
    } else {
      add(node + node + 1, mid + 1, r, i, id);
    }
  };
  vector<long long> dx(n);
  vector<long long> dy(n);
  function<void(int, int, int, int, int, int)> solve = [&](int node, int l, int r, int ll, int rr, int i) {
    if (l > r || l > rr || r < ll) return;
    if (ll <= l && r <= rr) {
      for (int id : ids[node]) {
        if (dx[id] <= dx[i] - high) {
          break;
        }
        ans.push_back(abs(x[i] - x[id]) + abs(y[i] - y[id]));
      }
      return;
    }
    int mid = l + r >> 1;
    solve(node + node, l, mid, ll, rr, i);
    solve(node + node + 1, mid + 1, r, ll, rr, i);
  };
  function<void(long long)> Construct = [&](long long d) {
    vector<tuple<long long, int, long long>> ev;
    vector<long long> xs;
    for (int i = 0; i < n; i++) {
      dx[i] = x[i] + y[i];
      dy[i] = x[i] - y[i];
      ev.emplace_back(dx[i], 0, i);
      ev.emplace_back(dx[i] + d, 1, i);
      xs.push_back(dy[i] - d);
      xs.push_back(dy[i] + d);
      xs.push_back(dy[i]);
    }
    sort(ev.begin(), ev.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int sz = xs.size();
    for (auto& e : ev) {
      int t = get<1>(e);
      int idx = get<2>(e);
      if (t == 0) {
        int aa = lower_bound(xs.begin(), xs.end(), dy[idx]) - xs.begin();
        add(1, 0, sz - 1, aa, idx);
      } else {
        int L = lower_bound(xs.begin(), xs.end(), dy[idx] - d) - xs.begin();
        int R = lower_bound(xs.begin(), xs.end(), dy[idx] + d) - xs.begin();
        solve(1, 0, sz - 1, L, R, idx);
      }
    }
    sort(ans.begin(), ans.end());
    vector<long long> tmp;
    for (int i = 0; i < ans.size(); i++) {
      if (ans[i] == 0) {
        continue;
      }
      tmp.push_back(ans[i]);
      i += 1;
    }
    ans = tmp;
  };
  Construct(high - 1);
  while (ans.size() < k) {
    ans.push_back(high);
  }
  for (int i = 0; i < k; i++) {
    if (i > 0) {
      cout << '\n';
    }
    cout << ans[i];
  }
  cout << '\n';
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp: In lambda function:
road_construction.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In lambda function:
road_construction.cpp:111:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |     int mid = l + r >> 1;
      |               ~~^~~
road_construction.cpp: In lambda function:
road_construction.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < ans.size(); i++) {
      |                     ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:155:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  155 |   while (ans.size() < k) {
      |          ~~~~~~~~~~~^~~

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