oj.uz

Submission #794818

# Submission time Handle Problem Language Result Execution time Memory
794818 2023-07-26T23:43:01 Z fuad27 Road Construction (JOI21_road_construction) C++17
100 / 100
 3463 ms 28900 KB 
#include<bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int N=250010;
int n, k;
vector<pair<long long,long long>> p;
vector<long long> res;
const long long inf=1e18;
bool check(long long dist) {
  res.clear();
  multiset<pair<long long, long long>> s;
  int p1=0;
  for(int i = 0;i<(int)p.size();i++) {
    while(p[i].first-p[p1].first>dist) {
      s.erase(s.find({p[p1].second, p[p1].first}));
      p1++;
    }
    auto it1=s.lower_bound({p[i].second-dist, -inf}), it2=s.upper_bound({p[i].second+dist+1, -inf});
    while(it1!=it2 and (int)res.size()<k) {
      res.push_back(max(abs(p[i].first-(*it1).second), abs(p[i].second-(*it1).first)));
      it1++;
    }
    s.insert({p[i].second, p[i].first});
  }
  return (int)res.size()==k;
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  for(int i = 0;i<n;i++) {
    long long x, y;
    cin >> x >> y;
    p.push_back({x+y, y-x});
  }
  sort(p.begin(), p.end());
  long long lo = 0, hi = 1e10;
  while(lo < hi) {
    long long mid=(lo+hi-1)>>1;
    if(check(mid)) {
      hi=mid;
    }
    else {
      lo=mid+1;
    }
  }
  check(lo-1);
  sort(res.begin(), res.end());
  for(long long i:res)cout << i << "\n";
  for(int i = res.size();i<k;i++)cout << lo << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5012 KB Output is correct
2 Correct 85 ms 5004 KB Output is correct
3 Correct 78 ms 4992 KB Output is correct
4 Correct 77 ms 5140 KB Output is correct
5 Correct 83 ms 3872 KB Output is correct
6 Correct 4 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 23052 KB Output is correct
2 Correct 882 ms 23004 KB Output is correct
3 Correct 69 ms 4944 KB Output is correct
4 Correct 859 ms 22824 KB Output is correct
5 Correct 960 ms 23000 KB Output is correct
6 Correct 983 ms 23008 KB Output is correct
7 Correct 914 ms 22232 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2293 ms 19856 KB Output is correct
2 Correct 2296 ms 19768 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 894 ms 19796 KB Output is correct
5 Correct 1931 ms 19848 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2293 ms 19856 KB Output is correct
2 Correct 2296 ms 19768 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 894 ms 19796 KB Output is correct
5 Correct 1931 ms 19848 KB Output is correct
6 Correct 2477 ms 19876 KB Output is correct
7 Correct 2584 ms 19840 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2363 ms 24972 KB Output is correct
11 Correct 932 ms 22824 KB Output is correct
12 Correct 1966 ms 25156 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5012 KB Output is correct
2 Correct 85 ms 5004 KB Output is correct
3 Correct 78 ms 4992 KB Output is correct
4 Correct 77 ms 5140 KB Output is correct
5 Correct 83 ms 3872 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 1250 ms 14056 KB Output is correct
8 Correct 1296 ms 14176 KB Output is correct
9 Correct 75 ms 5068 KB Output is correct
10 Correct 890 ms 13424 KB Output is correct
11 Correct 743 ms 13296 KB Output is correct
12 Correct 635 ms 14044 KB Output is correct
13 Correct 862 ms 12640 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5012 KB Output is correct
2 Correct 85 ms 5004 KB Output is correct
3 Correct 78 ms 4992 KB Output is correct
4 Correct 77 ms 5140 KB Output is correct
5 Correct 83 ms 3872 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 879 ms 23052 KB Output is correct
8 Correct 882 ms 23004 KB Output is correct
9 Correct 69 ms 4944 KB Output is correct
10 Correct 859 ms 22824 KB Output is correct
11 Correct 960 ms 23000 KB Output is correct
12 Correct 983 ms 23008 KB Output is correct
13 Correct 914 ms 22232 KB Output is correct
14 Correct 2293 ms 19856 KB Output is correct
15 Correct 2296 ms 19768 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 894 ms 19796 KB Output is correct
18 Correct 1931 ms 19848 KB Output is correct
19 Correct 2477 ms 19876 KB Output is correct
20 Correct 2584 ms 19840 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2363 ms 24972 KB Output is correct
24 Correct 932 ms 22824 KB Output is correct
25 Correct 1966 ms 25156 KB Output is correct
26 Correct 1250 ms 14056 KB Output is correct
27 Correct 1296 ms 14176 KB Output is correct
28 Correct 75 ms 5068 KB Output is correct
29 Correct 890 ms 13424 KB Output is correct
30 Correct 743 ms 13296 KB Output is correct
31 Correct 635 ms 14044 KB Output is correct
32 Correct 862 ms 12640 KB Output is correct
33 Correct 3330 ms 28860 KB Output is correct
34 Correct 3463 ms 28856 KB Output is correct
35 Correct 2656 ms 28096 KB Output is correct
36 Correct 1828 ms 28900 KB Output is correct
37 Correct 1924 ms 28860 KB Output is correct
38 Correct 2413 ms 27576 KB Output is correct