oj.uz

Submission #709451

# Submission time Handle Problem Language Result Execution time Memory
709451 2023-03-13T15:39:56 Z cig32 Road Construction (JOI21_road_construction) C++14
32 / 100
 2070 ms 81476 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 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 46 ms 6728 KB Output is correct
2 Correct 46 ms 6648 KB Output is correct
3 Correct 44 ms 6724 KB Output is correct
4 Correct 42 ms 6712 KB Output is correct
5 Correct 42 ms 5580 KB Output is correct
6 Correct 10 ms 1964 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 81412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 454 ms 81476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 454 ms 81476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6728 KB Output is correct
2 Correct 46 ms 6648 KB Output is correct
3 Correct 44 ms 6724 KB Output is correct
4 Correct 42 ms 6712 KB Output is correct
5 Correct 42 ms 5580 KB Output is correct
6 Correct 10 ms 1964 KB Output is correct
7 Correct 1244 ms 23572 KB Output is correct
8 Correct 1261 ms 23700 KB Output is correct
9 Correct 43 ms 6796 KB Output is correct
10 Correct 2070 ms 21280 KB Output is correct
11 Correct 1937 ms 22556 KB Output is correct
12 Correct 975 ms 9812 KB Output is correct
13 Correct 916 ms 12680 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6728 KB Output is correct
2 Correct 46 ms 6648 KB Output is correct
3 Correct 44 ms 6724 KB Output is correct
4 Correct 42 ms 6712 KB Output is correct
5 Correct 42 ms 5580 KB Output is correct
6 Correct 10 ms 1964 KB Output is correct
7 Runtime error 285 ms 81412 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -