1276번: 교각 놓기

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


$O(n(\lg n+c))$

교각을 높이를 기준으로 오름차순 정렬한다.
x 위치에 있는 교각의 최대 높이를 저장하는 배열을 만들어 해결한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, r, t[10000];
struct st { int l, r, h; }p[100];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d%d", &p[i].h, &p[i].l, &p[i].r);
    sort(p, p + n, [](st i, st j) {return i.h < j.h; });
    for (int i = 0; i < n; i++) {
        r += p[i].h * 2 - t[p[i].l] - t[p[i].r - 1];
        for (int j = p[i].l; j < p[i].r; j++) t[j] = p[i].h;
    }
    printf("%d", r);
    return 0;
}