Mock Silver S3 · "Sunrise Schedule"

← Back to mock contests · Original problem · Suggested time: 60–90 minutes

Problem

A train station has N trains, each with a known departure time d_i (in minutes from midnight) and a known travel time t_i. Each train arrives at its destination at time d_i + t_i.

Bessie arrives at the station at time S and can only board trains that depart at or after S. Find the earliest possible arrival time among trains she can board, or report −1 if no train works.

Then handle Q queries: for each query S_j, output the earliest arrival.

Constraints

1 ≤ N, Q ≤ 10⁵
0 ≤ d_i, t_i, S_j ≤ 10⁹
Time limit: 2 seconds

Sample

Input
4 3
10 5
12 1
20 30
15 10
8
12
21

Output
13
13
-1

Trains: arrivals are 15, 13, 50, 25. Query S=8: any train ok; earliest arrival = 13. Query S=12: trains with d ≥ 12 are (12,1)=13, (15,10)=25, (20,30)=50; earliest = 13. Query S=21: only (20,30)? No — d must be ≥ 21, none qualify. Answer: −1.

Skills this targets

Sorting + prefix-style data structure.
Binary search by key (find earliest train with d ≥ S).
Building a suffix-min array over arrivals.

Self-grade after attempting

Solution sketch (open after your timer is up)

Sort trains by departure d.
Suffix-min of arrivals. Walk the sorted array right-to-left, keeping the minimum of d_i + t_i seen so far. Call this minArr[i].
Per query. Binary-search the smallest index i with d_i ≥ S. Answer = minArr[i] if it exists, else −1.
Complexity: O((N + Q) log N). Fast at N = 10⁵.
Pitfall: Use long long — d + t can reach 2·10⁹.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<pair<long long, long long>> tr(N);
    for (auto& [d, t] : tr) cin >> d >> t;
    sort(tr.begin(), tr.end());                  // by d
    vector<long long> d(N), arr(N), minArr(N + 1, LLONG_MAX);
    for (int i = 0; i < N; ++i) { d[i] = tr[i].first; arr[i] = tr[i].first + tr[i].second; }
    for (int i = N - 1; i >= 0; --i) minArr[i] = min(minArr[i + 1], arr[i]);
    while (Q--) {
        long long S; cin >> S;
        int i = lower_bound(d.begin(), d.end(), S) - d.begin();
        cout << (i == N ? -1 : minArr[i]) << "\n";
    }
}