문제
실비아는 밀라노 센트랄레 기차역에 있었고 역이 많은 플랫폼을 가지고 있다는 것을 알았습니다. 그녀는 플랫폼이 너무 많다고 생각해서 실제로 몇 개가 필요한지 확인하기로 결정했습니다.
실비아는 또한 이 역에서 유지되는 흥미로운 사실을 알아냈습니다: 도착 및 출발의 일정이 매 두 날마다 반복되며 추가로 모든 n 대의 기차가 하루에 도착하고 떠납니다. 이렇게하면 모든 기차가 도착하기 전에 기차가 떠나지 않습니다.
역의 플랫폼은 모든 n 대의 기차를 동일한 플랫폼에 연이어 나열할 수 있을 만큼 충분히 깁니다. 그러나 기차 x가 먼저 플랫폼에 들어가고 그런 다음 기차 y가 들어가면 기차 x가 기차 y 앞에서 떠나지 못합니다.
도면은 두 번째 샘플 테스트의 플랫폼에서 가능한 기차 일정을 보여줍니다.
기차 'i : ai/bi'의 레이블은 i 번째 기차가 첫째 날에 역에 ai 번째 기차로 도착하고, 둘째 날에 bi 번째로 역을 떠난다는 것을 나타냅니다.
기차 (2 : 1/2)는 기차 (4 : 5/1)보다 먼저 플랫폼을 떠날 수 없습니다.
실비아는 모든 기차가 플랫폼에 나열될 수 있도록 필요한 최소 플랫폼 수가 무엇인지 궁금해졌습니다.
입력
첫 번째 줄에는 정수 n (1 ≤ n ≤ 2 · 105)이 주어지며, 기차의 수입니다.
두 번째 줄에는 n 개의 정수 ai (1 ≤ ai ≤ n, i ≠ j 일 때 ai ≠ aj)가 포함되어 있으며, i 번째 기차가 첫째 날에 역에 도착하는 순서를 나타냅니다. 시퀀스 (ai)는 순열입니다.
세 번째 줄에는 n 개의 정수 bi (1 ≤ bi ≤ n, i ̸= j 일 때 bi ̸= bj)가 포함되어 있으며, i 번째 기차가 둘째 날에 역을 떠나는 순서를 나타냅니다. 시퀀스 (bi)는 순열입니다.
출력
첫 번째 및 유일한 줄에 필요한 최소 플랫폼 수를 출력해야 합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 21점 | |
| #2 | 18점 | 최소 플랫폼 수는 |
| #3 | 31점 | |
| #4 | 30점 | 추가 제한 없음 |
예제 #1
5
3 5 2 4 1
3 2 5 1 4
2
예제 #2
5
3 1 2 5 4
4 2 3 1 5
4
예제 #3
3
3 2 1
1 2 3
1
로그인해야 코드를 작성할 수 있어요.