解法

概要

縦線をどこまで消すかをすべて試す。 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;
}