G - AtCoder Office

Contest Duration: 2024-08-03(Sat) 12:00 - 2024-08-03(Sat) 13:40 (local time) (100 minutes) Back to Home

G - AtCoder Office Editorial

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : $575$ 点

問題文

AtCoder 社のオフィスには $N$ 人の高橋くんが所属しています。

AtCoder 社ではオフィスの入退室の記録が取られており、記録が取られはじめてから $M$ 回の入退室が行われました。

$i$ 番目 $(1\leq i\leq M)$ の入退室記録は整数の組 $(T _ i,P _ i)$ で表され、時刻 $T _ i$ に $P _ i$ 番目の高橋くんがオフィスの外にいるならオフィスに入ったことを、オフィスの中にいるならオフィスから出たことを表します。

記録が取られはじめた時点ではどの高橋くんもオフィスの外におり、現在どの高橋くんもオフィスの外にいることがわかっています。

次の形式の $Q$ 個の質問に答えてください。

$i$ 番目 $(1\leq i\leq Q)$ の質問では整数の組 $(A _ i,B _ i)$ が与えられるので、記録を取っていた間に $A _ i$ 番目の高橋くんと $B _ i$ 番目の高橋くんがどちらもオフィスの中にいた時間の長さを求めてください。

制約

$2\leq N\leq2\times10 ^ 5$
$2\leq M\leq2\times10 ^ 5$
$1\leq T _ 1\lt T _ 2\lt\dotsb\lt T _ M\leq10 ^ 9$
$1\leq P _ i\leq N\ (1\leq i\leq M)$
どの $1\leq p\leq N$ についても、 $P _ i=p$ となる $i$ は偶数個存在する
$1\leq Q\leq2\times10 ^ 5$
$1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq Q)$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $T _ 1$   $P _ 1$ 
 $T _ 2$   $P _ 2$ 
 $\vdots$ 
 $T _ M$   $P _ M$ 
 $Q$ 
 $A _ 1$   $B _ 1$ 
 $A _ 2$   $B _ 2$ 
 $\vdots$ 
 $A _ Q$   $B _ Q$

出力

$Q$ 行にわたって出力せよ。 $i$ 行目 $(1\leq i\leq Q)$ には $i$ 番目の質問に対する答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

20
0
20

$3$ 人の高橋くんがオフィスの中にいた時間はそれぞれ以下の図のようになります。

それぞれの質問に対する答えは以下のようになります。

$1$ 番目の高橋くんと $2$ 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 $20$ から時刻 $30$ の間と時刻 $70$ から時刻 $80$ の間の $2$ 回です。長さはどちらも $10$ なので、これらの合計である $20$ を出力してください。
$1$ 番目の高橋くんと $3$ 番目の高橋くんが同時にオフィスの中にいたことはありません。よって、 $0$ を出力してください。
$2$ 番目の高橋くんと $3$ 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 $40$ から時刻 $60$ の間の $1$ 回です。長さは $20$ なので、 $20$ を出力してください。

入力例 2Copy

Copy

出力例 2Copy

Copy

Score : $575$ points

Problem Statement

$N$ people work at the AtCoder office.

The office keeps records of entries and exits, and there have been $M$ entries and exits since the records began.

The $i$ -th $(1\leq i\leq M)$ record is represented by a pair of integers $(T_i, P_i)$ , indicating that at time $T_i$ , the $P_i$ -th person either entered the office if they were outside, or exited the office if they were inside.

It is known that all people were outside the office at the beginning of the records, and they are outside now.

Answer $Q$ queries in the following format.

For the $i$ -th $(1\leq i\leq Q)$ query, you are given a pair of integers $(A_i, B_i)$ . Find the total length of the periods during which both the $A_i$ -th and $B_i$ -th persons were inside the office since the records began.

Constraints

$2\leq N\leq2\times10^5$
$2\leq M\leq2\times10^5$
$1\leq T_1\lt T_2\lt\dotsb\lt T_M\leq10^9$
$1\leq P_i\leq N\ (1\leq i\leq M)$
For every $1\leq p\leq N$ , the number of indices $i$ such that $P_i=p$ is even.
$1\leq Q\leq2\times10^5$
$1\leq A_i\lt B_i\leq N\ (1\leq i\leq Q)$
All inputs are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $M$ 
 $T_1$   $P_1$ 
 $T_2$   $P_2$ 
 $\vdots$ 
 $T_M$   $P_M$ 
 $Q$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
 $\vdots$ 
 $A_Q$   $B_Q$

Output

Print $Q$ lines. The $i$ -th line $(1\leq i\leq Q)$ should contain the answer to the $i$ -th query.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

20
0
20

The following diagram shows the time each of the three people spent inside the office.

The answers to each query are as follows:

The 1st and 2nd persons were both inside the office from time $20$ to time $30$ and from time $70$ to time $80$ . The lengths of these two periods are both $10$ , so print the total, which is $20$ .
The 1st and 3rd persons were never inside the office at the same time, so print $0$ .
The 2nd and 3rd persons were both inside the office from time $40$ to time $60$ . The length of this period is $20$ , so print $20$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy