백준 29618 - 미술 시간 (C++)

문제

• 문제 링크

  
   BOJ 29618 - 미술 시간 
  

• 문제 요약

칸의 길이 $N$과 아래와 같은 $Q$개의 쿼리가 주어진다.
모든 쿼리의 처리가 끝난 후 각 칸의 상태를 출력하자.



$a$ $b$ $x$ : $a$번째 칸부터 $b$번째 칸까지, 색칠되지 않은 칸을 $x$번 색으로 칠한다.




• 제한

TL : $0.5$ sec, ML : $512$ MB




$1 ≤ N, Q ≤ 100,000$

$1 ≤ x ≤ 10^9$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리를 사용한 집합과 맵 (tree _ set / map)

풀이

제한을 보면 당연히 나이브하게 돌 수 없다.

간단하게, $std::set$에서 색칠되지 않은 칸들을 들고 있다고 해보자.

그럼 임의의 쿼리 $a_i, b_i, x_i$에서 $a_i$의 위치를 $lower$_$bound$로 찾을 수 있다.
이후 $b_i$보다 작은 동안 찾아지는 모든 칸에 $x_i$를 기록하고, $set$에서 제거해주면 된다.

시간 복잡도는 $O(NlogN)$.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    set <int> S;
    for (int i(1); i <= n; S.insert(i++));
 
    vector <int> ans(n + 1);
    while (q--)
    {
        int a, b, x; cin >> a >> b >> x;
 
        queue <int> Q;
        for (auto it(S.lower_bound(a)); it != S.end() && *it <= b; it++)
            ans[*it] = x, Q.push(*it);
 
        for (; Q.size(); Q.pop())
            S.erase(Q.front());
    }
 
    for (int i(1); i <= n; cout << ans[i++] << ' ');
}

comment

끝