C - 照明の切り替え 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、大きなビルの照明管理システムを担当しています。このビルには N 個の部屋があり、各部屋には 1 から N までの番号が割り振られています。

各部屋の照明には「消灯」と「点灯」の 2 つの状態があります。初期状態では、すべての部屋の照明は消灯になっています。

高橋君は Q 回の操作を行います。i 回目 (1 \leq i \leq Q) の操作では、部屋番号が L_i 以上 R_i 以下であるすべての部屋に対して、照明の状態を反転させます。つまり、消灯ならば点灯に、点灯ならば消灯に切り替えます。

このビルには M 個の「会議室」があり、会議室の部屋番号は B_1, B_2, \ldots, B_M として与えられます（昇順とは限りません）。

すべての Q 回の操作が完了した後、会議室として指定された M 個の部屋のうち、照明が点灯している部屋の個数を求めてください。

制約

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq B_i \leq N (1 \leq i \leq M)
  • B_i はすべて異なる
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
  • 入力はすべて整数

入力

N M Q
B_1 B_2 \ldots B_M
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、部屋の総数を表す整数 N、会議室の個数を表す整数 M、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、会議室の部屋番号を表す M 個の整数 B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。
  • 3 行目以降の Q 行にわたって、各操作の情報が与えられる。
  • 2 + i 行目 (1 \leq i \leq Q) には、i 回目の操作で反転対象となる区間の始点 L_i と終点 R_i が、スペース区切りで与えられる。

出力

すべての操作が完了した後、会議室として指定された部屋のうち照明が点灯している部屋の個数を 1 行で出力してください。

入力例 1

10 3 2
2 5 8
1 6
4 9

出力例 1

2

入力例 2

20 5 4
3 7 12 15 18
1 10
5 15
8 12
3 7

出力例 2

2

入力例 3

1000000000 10 8
1 100 999999999 500000000 250000000 750000000 123456789 987654321 42 1000000000
1 500000000
250000000 750000000
100 123456789
42 42
500000000 1000000000
1 100
987654321 999999999
42 100

出力例 3

2

Score : 366 pts

Problem Statement

Takahashi is in charge of the lighting management system for a large building. The building has N rooms, and each room is assigned a number from 1 to N.

The lighting in each room has two states: "off" and "on". Initially, the lights in all rooms are off.

Takahashi performs Q operations. In the i-th operation (1 \leq i \leq Q), he toggles the lighting state of all rooms whose room numbers are between L_i and R_i, inclusive. That is, if a light is off, it is switched on, and if it is on, it is switched off.

The building has M "meeting rooms," and their room numbers are given as B_1, B_2, \ldots, B_M (not necessarily in ascending order).

After all Q operations have been completed, find the number of rooms among the M designated meeting rooms whose lights are on.

Constraints

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq B_i \leq N (1 \leq i \leq M)
  • All B_i are distinct
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
  • All input values are integers

Input

N M Q
B_1 B_2 \ldots B_M
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains three space-separated integers: N representing the total number of rooms, M representing the number of meeting rooms, and Q representing the number of operations.
  • The second line contains M space-separated integers B_1, B_2, \ldots, B_M representing the room numbers of the meeting rooms.
  • The following Q lines provide the information for each operation.
  • The (2 + i)-th line (1 \leq i \leq Q) contains two space-separated integers: the start L_i and end R_i of the interval to be toggled in the i-th operation.

Output

Print on a single line the number of meeting rooms whose lights are on after all operations have been completed.

Sample Input 1

10 3 2
2 5 8
1 6
4 9

Sample Output 1

2

Sample Input 2

20 5 4
3 7 12 15 18
1 10
5 15
8 12
3 7

Sample Output 2

2

Sample Input 3

1000000000 10 8
1 100 999999999 500000000 250000000 750000000 123456789 987654321 42 1000000000
1 500000000
250000000 750000000
100 123456789
42 42
500000000 1000000000
1 100
987654321 999999999
42 100

Sample Output 3

2