시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB43202052.632%

문제

An upcycled shipping container makes a good site to open a pop-up store in a trendy part of town. Such a business comes with its own risks -- for example, this morning a local freight company mistook your premises for one of their crates and sent it to the shipyard for loading.

Your crate is now sitting in the shipyard in one of two stacks ready for loading onto the ship. Each crate except yours has its own tracking number.

Figure H.1: Illustration of Sample Input 2. Your business is in the unmarked crate.

The system for loading crates is automated and proceeds in a preset order. First, the crate with the next tracking number is uncovered by picking up all of the crates on top, one-by-one, and moving every single one across to the other stack individually. Then the crate is taken to the ship. Since your crate is not part of this order, it is generally ignored and will not be loaded.

After loading a crate, some time is spent securing the whole cargo on board. This is your chance to recover your container -- if it is on top of one of the stacks, you will have just enough time to slide it off and get it back.

How many such opportunities will you have in total?

입력

The input consists of:

  • One line with three integers $n$, $s_1$ and $s_2$ ($2 \leq s_1, s_2 \leq 2 \cdot 10^{5}, s_1 + s_2 = n + 1$), the number of crates with a tracking number, the number of crates on the first stack, and the number of crates on the second stack respectively.
  • One line containing $s_1$ integers, the tracking numbers of the crates on the first stack, in order from bottom to top.
  • One line containing $s_2$ integers, the tracking numbers of the crates on the second stack, in order from bottom to top.

The crates with tracking number are numbered from $1$ to $n$ and are removed from the stacks in that order. Your crate has tracking number $0$ and will never be on top of one of the stacks initially.

출력

Output the number of occasions at which your crate is on top of one of the stacks and the crane is busy loading a crate.

예제 입력 1

4 3 2
2 0 3
1 4

예제 출력 1

3

예제 입력 2

6 4 3
2 4 0 1
6 3 5

예제 출력 2

4

Figure H.2: Step by step illustration of Sample Input 2. There are $4$ occasions at which your crate is on top of one of the stacks, while any of crates $1$, $4$, $5$ or $6$ is loaded.

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2021 H번

  • 문제를 만든 사람: Alexander Dietsch