Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1): A. The Tower is Going Home
解法
概要
縦線をどこまで消すかをすべて試す。 x軸方向に動ける範囲が固定されれば、横線を消す方法は一意。 これをやる。 実装はイベント処理的にすると楽。 \(O(n \log n)\)。
実装
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
int solve(int n, int m, vector<int> const & vr, vector<tuple<int, int, int> > const & hr) {
int cur = 0;
vector<pair<int, bool> > events;
for (auto it : hr) {
int x1, x2, y; tie(x1, x2, y) = it;
if (x1 != 1) continue;
++ cur;
if (x2 == 1000000000) continue;
events.emplace_back(x2, true);
}
for (int x : vr) {
events.emplace_back(x, false);
}
int answer = cur;
sort(ALL(events));
for (auto event : events) {
int x; bool is_hr; tie(x, is_hr) = event;
if (is_hr) {
-- cur;
} else {
++ cur;
}
chmin(answer, cur);
}
return answer;
}
int main() {
int n, m; cin >> n >> m;
vector<int> vr(n);
REP (i, n) cin >> vr[i];
vector<tuple<int, int, int> > hr(m);
REP (j, m) {
int x1, x2, y; cin >> x1 >> x2 >> y;
hr[j] = make_tuple(x1, x2, y);
}
cout << solve(n, m, vr, hr) << endl;
return 0;
}