fork download
copy 
  1. /// Social Distancing
  2. /// Author: Qwerty
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. const int MAXN = 1e5 + 100;
  6. int n, m;
  7. pair<long long, long long> a[MAXN];
  8. bool check(long long x){
  9.     int cnt = 1;
  10.     long long cur = a[cnt].first;
  11.     int f = 1;
  12.     while (cur + x <= a[m].second){
  13.         while (cur + x > a[cnt].second){
  14.             cnt++;
  15.         }
  16.         cur = max(cur + x, a[cnt].first);
  17.         f++;
  18.     }
  19.     return f >= n;
  20. }
  21. int main(){
  22.     //freopen("socdist.in", "r", stdin);
  23.     //freopen("socdist.out", "w", stdout);
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.     cin >> n >> m;
  27.     for (int i = 1; i <= m; i++){
  28.          cin >> a[i].first >> a[i].second;
  29.     }
  30.     sort(a + 1, a + m + 1);
  31.     long long lo = 1;
  32.     long long hi = 1e18;
  33.     long long ans = 0;
  34.     while (lo <= hi){
  35.         long long mid = (lo + hi) / 2;
  36.         if (check(mid)){
  37.             ans = max(ans, mid);
  38.             lo = mid + 1;
  39.         }
  40.         else hi = mid - 1;
  41.     }
  42.     cout << ans << '\n';
  43. }
  44.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
5 3
0 2
4 7
9 9
stdout
copy 
2
https://ideone.com/r4UblS
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!