레이팅 미적용사과 비가 내리고 있다! 특정 시각에 몇 개의 사과가 수직선 위에 떨어진다. 또 특정 시각에 농부 존의 소 몇 마리가 수직선 위에 도착하여 사과를 받기 시작한다.
사과가 떨어질 때 받아줄 소가 없으면 그 사과는 영원히 사라진다. 소와 사과가 같은 시각에 도착하면 소가 사과를 받는다. 각 소는 초당 한 단위씩 이동할 수 있다. 소는 사과 하나를 받으면 수직선에서 퇴장한다.
농부 존의 소들이 최적으로 협력한다면, 총 몇 개의 사과를 받을 수 있는가?
Problem credits: Benjamin Qi
Problem credits: Benjamin Qi
첫째 줄에 사과가 수직선에 떨어지거나 농부 존의 소가 나타나는 횟수 \(N\) (\(1\le N\le 2\cdot 10^5\))이 주어진다.
다음 \(N\)개의 줄에는 네 정수 \(q_i\), \(t_i\), \(x_i\), \(n_i\) (\(q_i\in \{1,2\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3\))가 주어진다.
- \(q_i=1\)이면, 농부 존의 소 \(n_i\)마리가 시각 \(t_i\)에 위치 \(x_i\)에서 수직선에 도착한다는 뜻이다.
- \(q_i=2\)이면, 사과 \(n_i\)개가 시각 \(t_i\)에 위치 \(x_i\)에서 수직선에 떨어진다는 뜻이다.
모든 순서쌍 \((t_i,x_i)\)는 서로 다름이 보장된다.
농부 존의 소들이 다 함께 받을 수 있는 사과의 최대 개수를 출력한다.
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 610In this example, none of the \(100\) apples that land at time \(t=5\) may be caught. Here is a way
for \(10\) apples to be caught:
- All six of FJ's cows that arrive at time \(t=4\) catch one of the apples that land at time \(t=8\).
- One of FJ's cows that arrive at time \(t=2\) catches one of the apples that land at time \(t=8\).
- Three of the remaining cows that arrive at time \(t=2\) catch one of the apples that land at time \(t=6\).
5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 69Here again, none of the apples that land at time \(t=5\) may be caught. Furthermore,
none of the cows that arrive at time \(t=2\) may catch any of the apples that land
at time \(t=8\). Here is a way for \(9\) apples to be caught:
- All six of FJ's cows that arrive at time \(t=4\) catch one of the apples that land at time \(t=8\).
- Three of the remaining cows that arrive at time \(t=2\) catch one of the apples that land at time \(t=6\).