5789. 현주의 상자 바꾸기

다른 풀이법으로 세그먼트 트리, 라인스위핑이 생각나긴 하는데 N,Q <= 1000 이라 O(NQ)기 때문에 들어오는대로 그때그때 처리해 주면 된다.

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
 
int t,n,q,a,b;
int arr[1001];
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n >> q;
        memset(arr, 0, sizeof(arr));
        for (int i = 1; i <= q; ++i) {
            cin >> a >> b;
            for (; a <= b; a++) arr[a] = i;
        }
        cout << "#" << tc << " ";
        for (int i = 1; i <= n; ++i) cout << arr[i] << " ";
        cout << '\n';
    }
    return 0;
}