oj.uz

Submission #969336

# Submission time Handle Problem Language Result Execution time Memory
969336 2024-04-25T02:26:50 Z abczz Road Construction (JOI21_road_construction) C++14
32 / 100
 3748 ms 27220 KB 
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#define ll long long

using namespace std;

ll n, k, f;
vector <ll> V;
map <pair<ll, ll>, ll> mp;
array <ll, 2> A[250000];
void solve(ll mid) {
  V.clear();
  mp.clear();
  f = 0;
  for (int i=0; i<n; ++i) {
    auto it = mp.lower_bound({A[i][0]-A[i][1]-mid, 0});
    while (it != mp.end()) {
      if (it->first.first > A[i][0]-A[i][1]+mid) break;
      auto nx = next(it);
      if (it->first.second + mid < A[i][0]+A[i][1]) mp.erase(it);
      else {
        auto x = (it->first.first+it->first.second)/2;
        V.push_back(abs(A[i][0]-x)+abs(A[i][1]-it->first.second+x));
        if (V.size() > k) break;
      }
      it = nx;
    }
    ++mp[{A[i][0]-A[i][1], A[i][0]+A[i][1]}];
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> k;
  for (int i=0; i<n; ++i) {
    cin >> A[i][0] >> A[i][1];
  }
  sort(A, A+n, [](auto a, auto b) {
    return a[0]+a[1] < b[0]+b[1];
  });
  ll l = 0, r = (ll)4e9, mid;
  while (l < r) {
    mid = (l+r)/2;
    solve(mid);
    if (V.size() < k) l = mid+1;
    else r = mid;
  }
  solve(l);
  sort(V.begin(), V.end());
  for (int i=0; i<k; ++i) {
    cout << V[i] << '\n';
  }
}

Compilation message

road_construction.cpp: In function 'void solve(long long int)':
road_construction.cpp:27:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |         if (V.size() > k) break;
      |             ~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:48:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   48 |     if (V.size() < k) l = mid+1;
      |         ~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5148 KB Output is correct
2 Correct 97 ms 5156 KB Output is correct
3 Correct 90 ms 5068 KB Output is correct
4 Correct 86 ms 5140 KB Output is correct
5 Correct 94 ms 3916 KB Output is correct
6 Correct 5 ms 604 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3717 ms 21908 KB Output is correct
2 Correct 3638 ms 27044 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1843 ms 24764 KB Output is correct
5 Correct 2219 ms 27068 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3717 ms 21908 KB Output is correct
2 Correct 3638 ms 27044 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1843 ms 24764 KB Output is correct
5 Correct 2219 ms 27068 KB Output is correct
6 Correct 3354 ms 26840 KB Output is correct
7 Correct 3538 ms 26844 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 3748 ms 26836 KB Output is correct
11 Correct 1947 ms 24772 KB Output is correct
12 Correct 2246 ms 27220 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5148 KB Output is correct
2 Correct 97 ms 5156 KB Output is correct
3 Correct 90 ms 5068 KB Output is correct
4 Correct 86 ms 5140 KB Output is correct
5 Correct 94 ms 3916 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 1018 ms 16400 KB Output is correct
8 Correct 960 ms 16068 KB Output is correct
9 Correct 85 ms 5068 KB Output is correct
10 Correct 969 ms 14988 KB Output is correct
11 Incorrect 1192 ms 14736 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5148 KB Output is correct
2 Correct 97 ms 5156 KB Output is correct
3 Correct 90 ms 5068 KB Output is correct
4 Correct 86 ms 5140 KB Output is correct
5 Correct 94 ms 3916 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Incorrect 2127 ms 24956 KB Output isn't correct
8 Halted 0 ms 0 KB -