Social Distancing

    1#include <bits/stdc++.h>
    2using namespace std;
    3bool good(long long d, int n, vector<pair<long long, long long>>& seg){
    4    long long cows = 0;
    5        long long last = 0;
    6        bool has_last = 0;
    7        for (auto &p : seg) {
    8            long long a = p.first, b = p.second;
    9            long long start;
    10            if (!has_last) {
    11                start = a;
    12            } else {
    13                start = max(a, last + d);
    14            }
    15            if (start > b) continue;
    16            long long diff = b - start;
    17            long long cnt = 1 + diff / d;
    18            cows += cnt;
    19            if (cows >= n) return true;
    20            long long new_last = start + (cnt - 1) * d;
    21            last = new_last;
    22            has_last = true;
    23        }
    24        return cows >= n;
    25}
    26int main(){
    27    ios::sync_with_stdio(0); cin.tie(0);
    28    int n, m; cin >> n >> m;
    29    vector<pair<long long, long long>> seg(m);
    30    for (int i = 0; i < m; i++) {
    31        long long a, b; cin >> a >> b;
    32        seg[i] = {a, b};
    33    }
    34    sort(seg.begin(), seg.end());
    35    long long lo = 1;
    36    long long hi = 1e18;
    37    while (lo < hi) {
    38        long long mid = lo + (hi - lo + 1) / 2;
    39        if (good(mid, n, seg)) lo = mid;
    40        else hi = mid - 1;
    41    }
    42    cout << lo << "\n";
    43    return 0;
    44}
    45