Telephone Charge [CODE FESTIVAL 2018 Final C]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_c

解説

https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3610538

条件で「全てのプランiに対して、通話時間がA[i]分の場合には他のどのプランよりも
通話料金が1円以上安くなることが保証されます。」という怪しい条件がある。
これをよくよく考えてみると、全てのプランa,bについてA[a]＜A[b]であれば、B[a]＜B[b]であるといえる。
加えて、全てのプランにおいて、増加率は1なので、ある2つの超過通話を比べると、Aが小さい方が必ずお得。
これを考慮すると、各クエリのTについて「T以上で一番近いAのプラン」か「T未満で一番近いAのプラン」
のどちらかが最適なプランである。
starts配列を使って、この2つのプランを特定しよう。
starts配列には{A,B}と入れておき、番兵も最初と最後に入れておく。
これでソートしておき、lower_boundで取ってくればいい。
あとは、2つのプランで小さい方が答え。

int N, A[101010], B[101010], M, T[101010];
vector<pair<ll, ll>> starts;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    starts.push_back({ -infl,infl });
    rep(i, 0, N) {
        cin >> A[i] >> B[i];
        starts.push_back({ A[i], B[i] });
    }
    starts.push_back({ infl,infl });
 
    sort(all(starts));
 
    cin >> M;
    rep(m, 0, M) {
        cin >> T[m];
 
        ll t = T[m];
 
        auto ite = lower_bound(all(starts), make_pair(t, -1LL));
 
        ll a = ite->first, b = ite->second;
        ite--;
        ll pa = ite->first, pb = ite->second;
 
        ll ans = b;
        chmin(ans, pb + (t - pa));
 
        printf("%lld\n", ans);
    }
}