oj.uz

답안 #554801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
554801 2022-04-29T12:49:15 Z MilosMilutinovic Road Construction (JOI21_road_construction) C++14
6 / 100
 10000 ms 149420 KB 
#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;
    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 q = ids[node].size() - 1; q >= 0; q--) {
        int id = ids[node][q];
        if (dx[id] <= dx[i] - high) {
          break;
        }
        ans.push_back(abs(x[i] - x[id]) + abs(y[i] - y[id]));
//        cout << i + 1 << " " << id + 1 << " " << ans.back() << endl;
      }
      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;
}

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 8768 KB Output is correct
2 Correct 87 ms 8664 KB Output is correct
3 Incorrect 80 ms 8592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8028 ms 146944 KB Output is correct
2 Correct 8002 ms 146532 KB Output is correct
3 Correct 74 ms 8588 KB Output is correct
4 Correct 7796 ms 149052 KB Output is correct
5 Correct 7735 ms 149308 KB Output is correct
6 Correct 7773 ms 149420 KB Output is correct
7 Correct 8035 ms 143792 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10083 ms 58752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10083 ms 58752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 8768 KB Output is correct
2 Correct 87 ms 8664 KB Output is correct
3 Incorrect 80 ms 8592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 8768 KB Output is correct
2 Correct 87 ms 8664 KB Output is correct
3 Incorrect 80 ms 8592 KB Output isn't correct
4 Halted 0 ms 0 KB -