백준 BOJ 15922 - 아우으 우아으이야!!

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

15922번: 아우으 우아으이야!!

지문이 이게뭐에요 ㄷㄷ(혼란)

입력으로 들어오는 선분들을 싹 훑으면서(스위핑이다) 진행한다.

현재 이어지고있는 수직선의 구간을 $[s, e]$ 로 저장해 뒀을 때,

새로 입력으로 들어오는 $[x, y]$ 에 대해서

$x <= e$ 인 경우 두 구간이 서로 겹치는 부분이 존재하기 때문에,

두 구간을 서로 이어붙여서

구간을 $[s, max(e,y)]$ 로 갱신한다.

 

서로 겹치는 구간이 없는 경우, $e < x$인 경우에는

지금 이어지고 있는 수직선 구간을 정답에 더해주고

새로 들어온 입력으로 구간을 갱신한다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<pair<int,int>> p;

int main(){
	int N,a,b;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a >> b;
		p.push_back({a,b});
	}
	
	int ans = 0;
	int s = p[0].x;
	int e = p[0].y;
	
	for(int i=1; i<N; i++){
		if(e >= p[i].x) e = max(p[i].y, e);
		else{
			ans += e-s;
			s = p[i].x;
			e = p[i].y;
		}
	}
	
	ans += e-s;
	cout << ans;
}