oj.uz

Submission #896202

# Submission time Handle Problem Language Result Execution time Memory
896202 2024-01-01T02:24:21 Z NeroZein Road Construction (JOI21_road_construction) C++17
59 / 100
 4155 ms 2097152 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    a[i] = make_pair(x + y, y - x); // rotate 45 degress
  }
  sort(a.begin(), a.end());
  long long lo = 0, hi = 4e9;
  while (lo < hi) {
    long long mid = (lo + hi) / 2;
    int p = 0, cnt = 0;
    multiset<int> se; 
    for (int i = 0; i < n && cnt < k; ++i) {
      auto [x, y] = a[i];
      while (p < i && (long long) x - a[p].first > mid) {
        se.erase(se.find(a[p].second));
        p++;
      }
      auto it = se.lower_bound(y - mid);
      while (it != se.end()) {
        int yy = *it;
        if ((long long) yy - y > mid) {
          break;
        } else {
          cnt++;
          it++; 
        }
      }
      se.insert(y);
    }
    if (cnt >= k) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  vector<long long> ans;
  multiset<pair<long long, int>> se; 
  for (int i = 0, p = 0; i < n; ++i) {
    auto [x, y] = a[i];
    while (p < i && (long long) x - a[p].first >= hi) {
      se.erase(se.find({a[p].second, a[p].first}));
      p++;
    }
    pair<long long, int> key = {(long long) y - hi, INT_MAX};
    auto it = se.lower_bound(key);
    while (it != se.end()) {
      auto [yy, xx] = *it;
      if ((long long) yy - y >= hi) {
        break;
      } else {
        ans.push_back(max(llabs((long long) y - yy), (long long) x - xx));
        it++;
      }
    }
    se.emplace(y, x);
  }
  sort(ans.begin(), ans.end());
  while ((int) ans.size() < k) {
    ans.push_back(hi);
  }
  for (int i = 0; i < k; ++i) {
    cout << ans[i] << '\n';
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7100 KB Output is correct
2 Correct 84 ms 7108 KB Output is correct
3 Correct 51 ms 5236 KB Output is correct
4 Correct 48 ms 5208 KB Output is correct
5 Correct 62 ms 6348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 5616 KB Output is correct
2 Correct 257 ms 5640 KB Output is correct
3 Correct 48 ms 5092 KB Output is correct
4 Correct 221 ms 8404 KB Output is correct
5 Runtime error 4155 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 7264 KB Output is correct
2 Correct 223 ms 7256 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 128 ms 5096 KB Output is correct
5 Correct 258 ms 7772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 7264 KB Output is correct
2 Correct 223 ms 7256 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 128 ms 5096 KB Output is correct
5 Correct 258 ms 7772 KB Output is correct
6 Correct 316 ms 7276 KB Output is correct
7 Correct 284 ms 7384 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 230 ms 7408 KB Output is correct
11 Correct 93 ms 5204 KB Output is correct
12 Correct 273 ms 7760 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7100 KB Output is correct
2 Correct 84 ms 7108 KB Output is correct
3 Correct 51 ms 5236 KB Output is correct
4 Correct 48 ms 5208 KB Output is correct
5 Correct 62 ms 6348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 588 ms 7292 KB Output is correct
8 Correct 573 ms 7280 KB Output is correct
9 Correct 48 ms 5152 KB Output is correct
10 Correct 341 ms 6524 KB Output is correct
11 Correct 199 ms 6408 KB Output is correct
12 Correct 212 ms 7588 KB Output is correct
13 Correct 276 ms 5844 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7100 KB Output is correct
2 Correct 84 ms 7108 KB Output is correct
3 Correct 51 ms 5236 KB Output is correct
4 Correct 48 ms 5208 KB Output is correct
5 Correct 62 ms 6348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 301 ms 5616 KB Output is correct
8 Correct 257 ms 5640 KB Output is correct
9 Correct 48 ms 5092 KB Output is correct
10 Correct 221 ms 8404 KB Output is correct
11 Runtime error 4155 ms 2097152 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -