Roadwork
問題はこちら
考え方
まずは、 に出発した人がどのような条件を満たした時に
の地点で通行止に引っかかるかを考えてみる。すると、1秒ごとに1進むので、以下の条件を満たしているときに通行止に引っかかるということが分かる。
これを愚直にやると、 箇所の通行止について、
人の出発時間を調べるので
のオーダーになり制限時間に間に合わない。
そこで、 各々の通行止区間について、そこで止まるものを取り除く という風に考えてみる。具体的には、一番手前で止まった場合はもうそれ以降の区間について考える必要がないので、調べる集合から取り除くことができるという考え。
なぜこれを行うと間に合うのか？
setでスタート時間を管理する。
- まず通行止区間を全て調べるので、ここに
。
- 各通行止区間について、
となるような
を
lower_boundで見つける。ここに。
となっている限り、
setからスタート時間を削除し、となる。ここは最大でも
回までしか回ることはない。要素の削除には
以上より、合計の計算量は になる。
具体的な実装
- structの
vectorとして、を管理。
の昇順にsortする。
- 各スタート時間とindexのpairを、
setにいれて管理。 - それぞれの通行止区間について、
を満たすような
- この時、別に答え出力用のanswer配列を用意しておき、
answer[index]にを代入する。
- この時、別に答え出力用のanswer配列を用意しておき、
- answerを出力する。
解答
抜粋部分
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(ll i = 0; i < (ll)(n); i++) struct stx { ll s, t, x; stx(ll s, ll t, ll x) : s(s), t(t), x(x) {} }; int main() { ll n, q; cin >> n >> q; vector<stx> v; rep(i, n) { ll s, t, x; cin >> s >> t >> x; stx temp(s, t, x); v.emplace_back(temp); } set<pair<ll, ll>> set1; rep(i, q) { ll d; cin >> d; set1.insert(pair<ll, ll>(d, i)); } auto comp = [](stx &a, stx &b) { if (a.x == b.x) { if (a.s == b.s) return a.t < b.t; return a.s < b.s; } return a.x < b.x; }; sort(v.begin(), v.end(), comp); vector<ll> ans(q, -1); rep(i, n) { ll s = v[i].s, x = v[i].x, t = v[i].t; auto it = set1.lower_bound(pair<ll, ll>(s - x, -1)); while (it != set1.end()) { if (t - x <= it->first) break; ans[it->second] = x; set1.erase(it++); } } rep(i, q) cout << ans[i] << endl; return 0; }
