oj.uz

Submission #709453

# Submission time Handle Problem Language Result Execution time Memory
709453 2023-03-13T15:40:55 Z cig32 Road Construction (JOI21_road_construction) C++14
100 / 100
 6146 ms 54408 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e5 + 2;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
bool cmp1(pair<int,int> x, pair<int,int> y) {
  return x.first+x.second < y.first+y.second;
}
bool cmp2(pair<int,int> x, pair<int,int> y) {
  return x.first-x.second < y.first-y.second;
}
int bit[MAXN];
void add(int x, int v) {
  for(;x<MAXN;x+=x&-x) bit[x] += v;
}
int sum(int x) {
  int s=0;
  for(;x;x-=x&-x) s += bit[x];
  return s;
}
void clear() {
  for(int i=0; i<MAXN; i++) bit[i] = 0;
}
int g[MAXN], w[MAXN], m;
int count(vector<pair<int,int> >v, int d) {
  int n = v.size();
  int ans=0;
  clear();
  int j=0;
  for(int i=0; i<v.size(); i++) {
    while(j<i && (v[i].first+v[i].second)-(v[j].first+v[j].second) > d) {
      add(w[j], -1);
      j++;
    }
    int l=1, r=m;
    while(l<r) {
      int mid=(l+r+1)>>1;
      if(g[mid]<=v[i].first-v[i].second+d) l=mid;
      else r=mid-1;
    }
    int ub = l;
    l=1, r=m;
    while(l<r) {
      int mid=(l+r)>>1;
      if(g[mid]>=v[i].first-v[i].second-d) r=mid;
      else l=mid+1;
    }
    int lb = l;
    ans += sum(ub) - (lb == 0 ? 0 : sum(lb-1));
    add(w[i], 1);
  }
  return ans;
}

vector<int> all(vector<pair<int,int> >v, int d) {
  int n = v.size();
  int j=0;
  vector<int> result;
  multiset<pair<int, int> > ms;
  for(int i=0; i<v.size(); i++) {
    while(j<i && (v[i].first+v[i].second)-(v[j].first+v[j].second) > d) {
      ms.erase(ms.lower_bound({v[j].first-v[j].second, v[j].first+v[j].second}));
      j++;
    }
    int ub = v[i].first-v[i].second+d, lb = v[i].first-v[i].second-d;
    if(ms.size()) {
      auto it = ms.lower_bound({lb, -4e9});
      while(it != ms.end() && (*it).first <= ub) {
        int x = abs((*it).first - (v[i].first - v[i].second));
        int y = abs((*it).second - (v[i].first + v[i].second));
        result.push_back(max(x, y));
        it++;
      }
    }
    ms.insert({v[i].first-v[i].second, v[i].first+v[i].second});
  }
  return result;
}
void solve(int tc) {
  int n, k;
  cin >> n >> k;
  vector<pair<int,int> > points;
  for(int i=0; i<n; i++) {
    int x, y;
    cin >> x >> y;
    points.push_back({x, y});
  }
  set<int>disc;
  for(int i=0; i<n; i++) {
    disc.insert(points[i].first-points[i].second);
  }
  sort(points.begin(), points.end(), cmp1);
  int it=1;
  map<int,int>is;
  for(int x: disc) {
    is[x] = it;
    g[it] = x;
    it++;
  }
  for(int i=0; i<n; i++) w[i] = is[points[i].first-points[i].second];
  m = it-1;
  
  int lb = 0, rb = 4e9;
  while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    int c = count(points, mid);
    if(c <= k) lb = mid;
    else rb = mid - 1;
  }
  vector<int> res = all(points, lb);
  sort(res.begin(), res.end());
  for(int x: res) cout << x << "\n";
  int finc = count(points, lb);
  if(finc < k) {
    rb = 4e9;
    lb++;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      int c = count(points, mid);
      if(c != finc) rb = mid;
      else lb = mid + 1;
    }
    for(int i=finc+1; i<=k; i++) cout << lb << "\n";
  }
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

road_construction.cpp: In function 'long long int count(std::vector<std::pair<long long int, long long int> >, long long int)':
road_construction.cpp:47:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~
road_construction.cpp:43:7: warning: unused variable 'n' [-Wunused-variable]
   43 |   int n = v.size();
      |       ^
road_construction.cpp: In function 'std::vector<long long int> all(std::vector<std::pair<long long int, long long int> >, long long int)':
road_construction.cpp:77:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~
road_construction.cpp:73:7: warning: unused variable 'n' [-Wunused-variable]
   73 |   int n = v.size();
      |       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9060 KB Output is correct
2 Correct 57 ms 9016 KB Output is correct
3 Correct 49 ms 9032 KB Output is correct
4 Correct 47 ms 9136 KB Output is correct
5 Correct 51 ms 7864 KB Output is correct
6 Correct 16 ms 4316 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3074 ms 48516 KB Output is correct
2 Correct 2939 ms 51612 KB Output is correct
3 Correct 45 ms 8912 KB Output is correct
4 Correct 2934 ms 51452 KB Output is correct
5 Correct 2838 ms 51584 KB Output is correct
6 Correct 2817 ms 51672 KB Output is correct
7 Correct 2830 ms 51032 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3499 ms 43352 KB Output is correct
2 Correct 3424 ms 48488 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 2941 ms 46292 KB Output is correct
5 Correct 2964 ms 19516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3499 ms 43352 KB Output is correct
2 Correct 3424 ms 48488 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 2941 ms 46292 KB Output is correct
5 Correct 2964 ms 19516 KB Output is correct
6 Correct 3485 ms 48480 KB Output is correct
7 Correct 3479 ms 48636 KB Output is correct
8 Correct 5 ms 4180 KB Output is correct
9 Correct 6 ms 4172 KB Output is correct
10 Correct 3379 ms 46188 KB Output is correct
11 Correct 2797 ms 46296 KB Output is correct
12 Correct 2926 ms 19516 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9060 KB Output is correct
2 Correct 57 ms 9016 KB Output is correct
3 Correct 49 ms 9032 KB Output is correct
4 Correct 47 ms 9136 KB Output is correct
5 Correct 51 ms 7864 KB Output is correct
6 Correct 16 ms 4316 KB Output is correct
7 Correct 1260 ms 25848 KB Output is correct
8 Correct 1267 ms 25988 KB Output is correct
9 Correct 50 ms 9140 KB Output is correct
10 Correct 2195 ms 23612 KB Output is correct
11 Correct 2142 ms 22816 KB Output is correct
12 Correct 1092 ms 10188 KB Output is correct
13 Correct 1035 ms 12900 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9060 KB Output is correct
2 Correct 57 ms 9016 KB Output is correct
3 Correct 49 ms 9032 KB Output is correct
4 Correct 47 ms 9136 KB Output is correct
5 Correct 51 ms 7864 KB Output is correct
6 Correct 16 ms 4316 KB Output is correct
7 Correct 3074 ms 48516 KB Output is correct
8 Correct 2939 ms 51612 KB Output is correct
9 Correct 45 ms 8912 KB Output is correct
10 Correct 2934 ms 51452 KB Output is correct
11 Correct 2838 ms 51584 KB Output is correct
12 Correct 2817 ms 51672 KB Output is correct
13 Correct 2830 ms 51032 KB Output is correct
14 Correct 3499 ms 43352 KB Output is correct
15 Correct 3424 ms 48488 KB Output is correct
16 Correct 5 ms 4180 KB Output is correct
17 Correct 2941 ms 46292 KB Output is correct
18 Correct 2964 ms 19516 KB Output is correct
19 Correct 3485 ms 48480 KB Output is correct
20 Correct 3479 ms 48636 KB Output is correct
21 Correct 5 ms 4180 KB Output is correct
22 Correct 6 ms 4172 KB Output is correct
23 Correct 3379 ms 46188 KB Output is correct
24 Correct 2797 ms 46296 KB Output is correct
25 Correct 2926 ms 19516 KB Output is correct
26 Correct 1260 ms 25848 KB Output is correct
27 Correct 1267 ms 25988 KB Output is correct
28 Correct 50 ms 9140 KB Output is correct
29 Correct 2195 ms 23612 KB Output is correct
30 Correct 2142 ms 22816 KB Output is correct
31 Correct 1092 ms 10188 KB Output is correct
32 Correct 1035 ms 12900 KB Output is correct
33 Correct 3540 ms 54364 KB Output is correct
34 Correct 3768 ms 54408 KB Output is correct
35 Correct 6146 ms 46588 KB Output is correct
36 Correct 2770 ms 21176 KB Output is correct
37 Correct 2902 ms 21136 KB Output is correct
38 Correct 2920 ms 24012 KB Output is correct