Submission #46827796

---

Source Code Expand

#include <bits/stdc++.h>

void solve(std::istream& is, std::ostream& os) {
    using Num = long long int;
    Num n {0};
    is >> n;

    std::vector<std::pair<Num, Num>> pre;
    for(Num i{0}; i<n; ++i) {
        Num t {0};
        Num d {0};
        is >> t >> d;
        pre.push_back(std::make_pair(t, t+d));
    }
    std::sort(pre.begin(), pre.end());

    Num answer {0};
    Num index {0};
    Num current = pre.begin()->first;
    std::priority_queue<Num, std::vector<Num>, std::greater<Num>> q;
    while(index < n) {
        if (q.empty()) {
            if (index < n) {
                current = std::max(current, pre.at(index).first);
            }
        }

        while(index < n) {
            if (pre.at(index).first <= current) {
                q.push(pre.at(index).second);
                ++index;
            } else {
                break;
            }
        }

        while (!q.empty()) {
            const auto t = q.top();
            q.pop();

            if (t >= current) {
                ++answer;
                ++current;
            }

            if (index < n) {
                if (current >= pre.at(index).first) {
                    break;
                }
            }
        }
    }

    os << answer << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result