oj.uz

Submission #697176

# Submission time Handle Problem Language Result Execution time Memory
697176 2023-02-08T17:28:45 Z peijar Road Construction (JOI21_road_construction) C++17
100 / 100
 6736 ms 19288 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

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

  int N, K;
  cin >> N >> K;
  K *= 2;
  vector<pair<int, int>> points(N);
  for (auto &[x, y] : points) {
    cin >> x >> y;
    tie(x, y) = make_pair(x - y, x + y);
  }

  vector<int> valY;
  for (auto [x, y] : points)
    valY.push_back(y);

  sort(valY.begin(), valY.end());
  valY.resize(unique(valY.begin(), valY.end()) - valY.begin());
  int nbY = valY.size();

  auto getId = [&](int y) {
    return lower_bound(valY.begin(), valY.end(), y) - valY.begin();
  };
  sort(points.begin(), points.end());

  auto countSmaller = [&](int L) { // cb avec dis <= L?
    int sol = 0;
    Fenwick<int> fen(nbY);

    int l = 0, r = 0;
    for (auto [x, y] : points) {
      while (r < N and points[r].first <= x + L)
        fen.upd(getId(points[r++].second), 1);
      while (l < r and points[l].first < x - L) {
        fen.upd(getId(points[l++].second), -1);
      }
      assert(l < r);

      int fstGood = lower_bound(valY.begin(), valY.end(), y - L) - valY.begin();
      int fstBad = upper_bound(valY.begin(), valY.end(), y + L) - valY.begin();
      sol += fen.sum(fstGood, fstBad) - 1;
    }
    return sol;
  };

  int lo = 0, up = 1e18;
  while (lo < up) {
    int mid = (lo + up + 1) / 2;

    if (countSmaller(mid) <= K)
      lo = mid;
    else
      up = mid - 1;
  }

  int L = lo;
  vector<int> costs;
  int add = K - countSmaller(L);
  for (int i = 0; i < add; ++i)
    costs.push_back(L + 1);

  int l = 0, r = 0;
  set<pair<int, int>> possible;
  for (int i = 0; i < N; ++i) {
    auto [x, y] = points[i];
    while (r < N and points[r].first <= x + L) {
      possible.emplace(points[r].second, r);
      ++r;
    }
    while (l < r and points[l].first < x - L) {
      possible.erase({points[l].second, l});
      ++l;
    }
    for (auto it = possible.lower_bound(pair(y - L, 0));
         it != possible.end() and it->first <= y + L; ++it) {
      auto [x2, y2] = points[it->second];
      if (i != it->second)
        costs.push_back(max(abs(x2 - x), abs(y2 - y)));
    }
  }
  sort(costs.begin(), costs.end());
  for (int i = 0; i < K; i += 2)
    cout << costs[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7004 KB Output is correct
2 Correct 70 ms 6980 KB Output is correct
3 Correct 63 ms 7212 KB Output is correct
4 Correct 64 ms 7132 KB Output is correct
5 Correct 61 ms 5852 KB Output is correct
6 Correct 3 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2706 ms 16396 KB Output is correct
2 Correct 2616 ms 16356 KB Output is correct
3 Correct 55 ms 6852 KB Output is correct
4 Correct 2637 ms 16168 KB Output is correct
5 Correct 2466 ms 16332 KB Output is correct
6 Correct 2512 ms 16436 KB Output is correct
7 Correct 2586 ms 15836 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6149 ms 13368 KB Output is correct
2 Correct 6195 ms 13372 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2479 ms 11132 KB Output is correct
5 Correct 1891 ms 11648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6149 ms 13368 KB Output is correct
2 Correct 6195 ms 13372 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2479 ms 11132 KB Output is correct
5 Correct 1891 ms 11648 KB Output is correct
6 Correct 6237 ms 13252 KB Output is correct
7 Correct 6296 ms 13376 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 6106 ms 13124 KB Output is correct
11 Correct 2483 ms 11132 KB Output is correct
12 Correct 1847 ms 11644 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7004 KB Output is correct
2 Correct 70 ms 6980 KB Output is correct
3 Correct 63 ms 7212 KB Output is correct
4 Correct 64 ms 7132 KB Output is correct
5 Correct 61 ms 5852 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2434 ms 11684 KB Output is correct
8 Correct 2469 ms 11720 KB Output is correct
9 Correct 69 ms 7080 KB Output is correct
10 Correct 2321 ms 10880 KB Output is correct
11 Correct 2076 ms 10704 KB Output is correct
12 Correct 626 ms 10700 KB Output is correct
13 Correct 757 ms 9372 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7004 KB Output is correct
2 Correct 70 ms 6980 KB Output is correct
3 Correct 63 ms 7212 KB Output is correct
4 Correct 64 ms 7132 KB Output is correct
5 Correct 61 ms 5852 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2706 ms 16396 KB Output is correct
8 Correct 2616 ms 16356 KB Output is correct
9 Correct 55 ms 6852 KB Output is correct
10 Correct 2637 ms 16168 KB Output is correct
11 Correct 2466 ms 16332 KB Output is correct
12 Correct 2512 ms 16436 KB Output is correct
13 Correct 2586 ms 15836 KB Output is correct
14 Correct 6149 ms 13368 KB Output is correct
15 Correct 6195 ms 13372 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2479 ms 11132 KB Output is correct
18 Correct 1891 ms 11648 KB Output is correct
19 Correct 6237 ms 13252 KB Output is correct
20 Correct 6296 ms 13376 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 6106 ms 13124 KB Output is correct
24 Correct 2483 ms 11132 KB Output is correct
25 Correct 1847 ms 11644 KB Output is correct
26 Correct 2434 ms 11684 KB Output is correct
27 Correct 2469 ms 11720 KB Output is correct
28 Correct 69 ms 7080 KB Output is correct
29 Correct 2321 ms 10880 KB Output is correct
30 Correct 2076 ms 10704 KB Output is correct
31 Correct 626 ms 10700 KB Output is correct
32 Correct 757 ms 9372 KB Output is correct
33 Correct 6698 ms 19248 KB Output is correct
34 Correct 6736 ms 19288 KB Output is correct
35 Correct 6282 ms 18516 KB Output is correct
36 Correct 1569 ms 17340 KB Output is correct
37 Correct 1629 ms 17300 KB Output is correct
38 Correct 1938 ms 17936 KB Output is correct