CODE FESTIVAL 2018 Final (Parallel) C - Telephone Charge

結構難しいlower_boundですが、面白い使い方を見つけたので、使ってみました。

イテレータから値を取り出す書き方は、auto x=*lower_bound(.....)といった*を使う方法しか知っていましたが、

一旦auto it=lower_bound(.....)とイテレータ自体を変数で受け取っておいてから,

it[0],it[-1],it[1]と前後の値も配列のように取り出す方法は知りませんでした。

配列の端っこのコーナケースを処理するのに便利そうです。

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i, n) for (int i = 0; i < (n); i++)

int inf = 1e18;

struct charge {

int a, b;

charge(){};

charge(int a_, int b_) { a = a_, b = b_; };

bool operator<(const charge& o) const { return a < o.a; }

};

signed main() {

int n, m;

cin >> n;

vector<charge> c;

rep(i, n) {

int a, b;

cin >> a >> b;

c.push_back({a, b});

}

cin >> m;

vector<int> t(m);

for (auto&& u : t) cin >> u;

sort(begin(c), end(c));

rep(i, m) {

auto it = lower_bound(begin(c), end(c), charge(t[i], -1));

if (it == c.begin())

cout << it[0].b << endl;

else if (it == c.end())

cout << (it[-1].b + t[i] - it[-1].a) << endl;

else

cout << min(it[-1].b + t[i] - it[-1].a, it[0].b) << endl;

}

}