4003번: 경비병

https://www.acmicpc.net/problem/4003


$O(n+m\lg m)$

'i번째 덤불에 닌자가 확실히 있다.'
<->
'i번째 덤불에 닌자가 없다면 주어진 조건에 모순이 생긴다.'

따라서 i번째 덤불에 닌자가 없다고 가정한 뒤, 주어진 조건에 따라 k가 배치할 수 있는 닌자들 수의 최댓값과 최솟값 사이에 있는지 판별하면 된다.

배치 가능한 닌자들의 최댓값은 경비병이 닌자가 없다고 한 구간을 제외하고 나머지 덤불에 모두 배치한 닌자의 수이다. 당연하게도 k는 이 값보다 작거나 같으며 같은 경우에는 해당 덤불 모두에 닌자가 존재한다.

배치 가능한 닌자들의 최솟값은 그리디 알고리즘을 통해 구할 수 있다.
i번째 경비병의 정보를 통해 닌자가 존재할 수 있는 덤불 위치의 최솟값을 sli, 최댓값을 sri라 하자.
배치된 닌자들의 수가 최소가 될 때, 왼쪽으로부터 i번째인 닌자를 최대한 오른쪽으로 배치했을 때 위치 r[i]라 하자. 그러면 r[i]는 r[i-1]<slj인 정보들 중 srj의 최솟값이 된다. 비슷한 방법으로 왼쪽으로부터 i번째인 닌자를 최대한 왼쪽으로 배치했을 때 위치 l[i]를 구할 수 있고 배치된 닌자들의 최솟값도 구할 수 있다.

이 최솟값을 t라고 하자. 다음 두 경우가 존재한다.
i) t=k
l[i]=r[i]인 덤불에 닌자가 확실히 있다.
ii) t<k
sl[i]=sr[i]인 덤불에 닌자가 확실히 있다.
sl[i]<sr[i]일 때는 해당 덤불 구간 중 한 덤불에 닌자가 없다고 가정해도 나머지 덤불에 적절히 닌자를 배치하면 가능하기 때문이다. 이 때 추가될 닌자는 많아야 2명이다.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int MXN = 1e5;
int n, k, m, s[MXN + 2];
vector<pair<int, int> > sg;
vector<int> sl, sr, l, r, v, res;
int main() {
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (c) sg.push_back({ b,-a });
        else s[a]++, s[b + 1]--;
    }
    for (int i = 1; i <= n; i++) if (!(s[i] += s[i - 1])) v.push_back(i);
    sort(sg.begin(), sg.end());
    for (int i = 0, t = 0, lp = 0, rp = 0; i<sg.size(); i++) if (t > sg[i].second) {
        t = sg[i].second;
        for (; v[lp] < -t; lp++);
        for (; rp < v.size() && v[rp] <= sg[i].first; rp++);
        sl.push_back(v[lp]);
        sr.push_back(v[rp - 1]);
    }
    for (int i = 0, t = 0; i < sl.size(); i++) if (t < sl[i]) r.push_back(t = sr[i]);
    for (int i = sl.size(), t = n + 1; i--;) if (t > sr[i]) l.push_back(t = sl[i]);
    if (v.size() == k) res = v;
    else if (r.size() == k) {
        for (int i = 0; i < r.size(); i++) if (r[i] == l[r.size() - 1 - i]) res.push_back(r[i]);
    }
    else {
        for (int i = 0; i < sr.size(); i++) if (sl[i] == sr[i]) res.push_back(sr[i]);
    }
    if (res.empty()) puts("-1");
    else for (auto it : res) printf("%d\n", it);
    return 0;
}