oj.uz

Submission #554710

# Submission time Handle Problem Language Result Execution time Memory
554710 2022-04-29T08:52:58 Z MilosMilutinovic Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 64064 KB 
/* todo */
#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, dy + d + 1);
      ev.emplace_back(dx + d + 1, 1, dy - d, dy + d + 1);
      ev.emplace_back(dx, 2, dy, dy);
      xs.push_back(dy - d);
      xs.push_back(dy + d + 1);
      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);
      }
    }
    if (d == 4) {
      cout << cnt << '\n';
    }
    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;
    }
  }
  cout << high << '\n';
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7491 ms 62044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10070 ms 64064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10070 ms 64064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -