https://www.acmicpc.net/problem/16357 을 3개고르는거로 확장 & 가로대신 세로

[문제]
벽돌을 나타내는 x축에 평행한 N개의 선분이 주어진다.
3번의 격파를 통해 최대한 많은 벽돌을 부셔라.

격파는 다음과 같이 진행된다.
1. 격파할 x좌표를 고른다.
2. 고른 x좌표에 대해 y축방향(세로)으로 지나는 모든 벽돌을 부신다.

한 벽돌을 여러번 격파해도 하나의 벽돌이 부서진것으로 생각한다.

[제한]
N=300'000
0 <= x_i,y_i < 300'000

[풀이]
어떠한 3번의 격파중에 중간에 하는 격파를 고정하면 16357의 풀이와 똑같이 스위핑하면서 왼쪽최대와 오른쪽최대를 구할 수 있다. 끝