【題解】Google Kick Start 2020 Round F Metal Harvest

#include <iostream>
#include <algorithm>
using namespace std;

int t, n, k, a[100005], s[100005], e[100005];

bool cmp(int x, int y){
    return s[x] < s[y];
}

int main() {
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cin >> n >> k;
        for (int i = 0; i < n; i++){
            cin >> s[i] >> e[i];
            a[i] = i;
        }
        sort(a, a+n, cmp);
        int ans = 0;
        long long r = 0;
        for (int i = 0; i < n; i++){
            if (e[a[i]] <= r) continue;
            if (r < s[a[i]]) r = s[a[i]];
            long long tmp = e[a[i]]-r;
            tmp = (tmp-1)/k+1;
            ans += tmp;
            r += tmp*k;
        }
        cout << "Case #" << Case << ": " << ans << "\n";
    }
}