백준 6242, STL
USACO 정해는 항상 배울점이 많지만, 이 문제는 더욱 배울점이 많다.
STL을 이렇게 우아하게 사용한 것이 놀랍다.
위치 $x$ 에서 그림자의 높이는 $x$ 를 포함하는 모든 건물들 중 가장 높은 건물의 높이다.
$map$ 을 통해 건물이 시작하는 위치 $s$ 에서 높이를 추가하고, 끝나는 위치 $e$ 에서 높이를 제거하면서 $multiset$ 을 유지하면 된다.
Source Code
//BOJ 6242
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
map<int, vector<pll>> mp;
multiset<ll, greater<ll>> st;
int N;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for (int i = 0; i < N; ++i) {
ll s, e, height;
cin >> s >> e >> height;
mp[s].push_back({ height, 1 });
mp[e].push_back({ height, 0 });
}
ll spoint, epoint, ans;
spoint = 1;
epoint = 1;
ans = 0;
for (auto it = mp.begin(); it != mp.end(); ++it) {
epoint = it->first;
if (!st.empty()) ans += (epoint - spoint) * (*st.begin());
spoint = epoint;
for (int i = 0; i < (it->second).size(); ++i) {
ll height, open;
height = it->second[i].first;
open = it->second[i].second;
if (open) {
st.emplace(height);
}
else {
if(!st.empty()) st.erase(st.find(height));
}
}
}
printf("%lld\n", ans);
}