-
2170, Gold 5백준 2021. 10. 3. 00:29
문제
- $n(1\leq n \leq 10^{6})$번 수직선 위의 구간 $[x, y], -10^{9}\leq x < y \leq 10^{9}$에 선분을 긋는다
- 그려진 선들의 길이의 합?
$O(nlog\ n)$
선분들을 정렬한 후 $O(nlog\ n)$
선분들이 하나의 연속된 그룹(두 선분 사이에 빈틈이 없으면 연속이라 하자)인지 아닌지를 판단한다 $O(n)$i) $s \leq r$이면 연속
ii) $r < s$이면 불연속
c++
1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>#define endl "\n"#define ooop(i, n) for(int i = 0; i < n; i++)#define loop(i, n) for(int i = 1; i <= n; i++)using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;int n;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;vector<pii> v(n);for(auto& e: v) cin >> e.first >> e.second;sort(v.begin(), v.end());int s, e, res = 0, l = -1e9-1, r = -1e9-1;for(auto [s, e]: v){if(r < s){res += r-l;l = s; r = e;}else{r = max(r, e);}}res += r-l;cout << res << endl;return 0;}cspython3
123456789101112import sysn = int(input())d = sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(n)])l, r = int(-1e9-1), int(-1e9-1)res = 0for s, e in d:if s <= r: r = max(r, e)else:res += r-ll, r = s, e참고
'백준' 카테고리의 다른 글
11286, Silver 1 (0) 2021.10.03 15589, Gold 1 (0) 2021.10.03 16768, Gold 4 (0) 2021.09.21 1654, Silver 3 (0) 2021.09.15 11047, Silver 2 (0) 2021.08.19