103053: [Atcoder]ABC305 D - Sleep Log
Description
Score : $450$ points
Problem Statement
Takahashi keeps a sleep log. The log is represented as an odd-length sequence $A=(A _ 1(=0), A _ 2,\ldots,A _ N)$, where odd-numbered elements represent times he got up, and even-numbered elements represent times he went to bed. More formally, he had the following sleep sessions after starting the sleep log.
- For every integer $i$ such that $1\leq i\leq\dfrac{N-1}2$, he fell asleep exactly $A _ {2i}$ minutes after starting the sleep log and woke up exactly $A _ {2i+1}$ minutes after starting the sleep log.
- He did not fall asleep or wake up at any other time.
Answer the following $Q$ questions. For the $i$-th question, you are given a pair of integers $(l _ i,r _ i)$ such that $0\leq l _ i\leq r _ i\leq A _ N$.
- What is the total number of minutes for which Takahashi was asleep during the $r _ i-l _ i$ minutes from exactly $l _ i$ minutes to $r _ i$ minutes after starting the sleep log?
Constraints
- $3\leq N\lt2\times10^5$
- $N$ is odd.
- $0=A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^9$
- $1\leq Q\leq2\times10^5$
- $0\leq l _ i\leq r _ i\leq A _ N\ (1\leq i\leq Q)$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $Q$ $l _ 1$ $r _ 1$ $l _ 2$ $r _ 2$ $\vdots$ $l _ Q$ $r _ Q$
Output
Print the answer in $Q$ lines. The $i$-th line should contain an integer answering to the $i$-th question.
Sample Input 1
7 0 240 720 1320 1440 1800 2160 3 480 1920 720 1200 0 2160
Sample Output 1
480 0 960
Takahashi slept as shown in the following figure.
The answers to each question are as follows.
- Between $480$ minutes and $1920$ minutes after starting the sleep log, Takahashi slept from $480$ minutes to $720$ minutes, from $1320$ minutes to $1440$ minutes, and from $1800$ minutes to $1920$ minutes in $3$ sleep sessions. The total sleep time is $240+120+120=480$ minutes.
- Between $720$ minutes and $1200$ minutes after starting the sleep log, Takahashi did not sleep. The total sleep time is $0$ minutes.
- Between $0$ minutes and $2160$ minutes after starting the sleep log, Takahashi slept from $240$ minutes to $720$ minutes, from $1320$ minutes to $1440$ minutes, and from $1800$ minutes to $2160$ minutes in $3$ sleep sessions. The total sleep time is $480+120+360=960$ minutes.
Therefore, the three lines of the output should contain $480$, $0$, and $960$.
Sample Input 2
21 0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000 10 77 721 255 541 478 970 369 466 343 541 42 165 16 618 222 592 730 983 338 747
Sample Output 2
296 150 150 49 89 20 279 183 61 177
Input
题意翻译
高桥君的睡眠记录可以用一个长度为奇数 $N$ 的序列 $A_1,A_2,\cdots,A_N$ 描述: - 如果下标为奇数,则代表他从这个时间点停止睡觉; - 如果下标为偶数,则代表他从这个时间点开始睡觉。 保证 $A_1=0$。有 $Q$ 次询问,每次询问会给出两个非负整数 $l \le r$,你需要回答在 $[l,r)$ 这段时间内高桥君睡觉时间的总和是多少。Output
问题描述
高桥君保存了一份睡眠日志。日志用一个奇数长度的序列$A=(A _ 1(=0), A _ 2,\ldots,A _ N)$表示,其中奇数项表示他起床的时间,偶数项表示他睡觉的时间。 更正式地说,他在开始睡眠日志后,进行了以下睡眠会话。
- 对于每一个满足$1\leq i\leq\dfrac{N-1}2$的整数$i$,他会在开始睡眠日志后$A _ {2i}$分钟入睡,在开始睡眠日志后$A _ {2i+1}$分钟醒来。
- 他在其他任何时间都没有入睡或醒来。
回答以下$Q$个问题。 对于第$i$个问题,你会得到一对整数$(l _ i,r _ i)$,满足$0\leq l _ i\leq r _ i\leq A _ N$。
- 在开始睡眠日志后的$l _ i$分钟到$r _ i$分钟的$r _ i-l _ i$分钟内,高桥君总共睡了多少分钟?
约束
- $3\leq N\lt2\times10^5$
- $N$是奇数。
- $0=A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^9$
- $1\leq Q\leq2\times10^5$
- $0\leq l _ i\leq r _ i\leq A _ N\ (1\leq i\leq Q)$
- 所有的输入值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$ $Q$ $l _ 1$ $r _ 1$ $l _ 2$ $r _ 2$ $\vdots$ $l _ Q$ $r _ Q$
输出
在$Q$行中打印答案。 第$i$行应该包含回答第$i$个问题的整数。
样例输入1
7 0 240 720 1320 1440 1800 2160 3 480 1920 720 1200 0 2160
样例输出1
480 0 960
高桥君的睡眠情况如下图所示。
每个问题的答案如下。
- 在开始睡眠日志后的480分钟到1920分钟之间,高桥君在480分钟到720分钟,1320分钟到1440分钟,1800分钟到1920分钟的3次睡眠中睡了3次。总睡眠时间是$240+120+120=480$分钟。
- 在开始睡眠日志后的720分钟到1200分钟之间,高桥君没有睡觉。总睡眠时间是$0$分钟。
- 在开始睡眠日志后的0分钟到2160分钟之间,高桥君在240分钟到720分钟,1320分钟到1440分钟,1800分钟到2160分钟的3次睡眠中睡了3次。总睡眠时间是$480+120+360=960$分钟。
因此,输出的前三行应该是$480$,$0$和$960$。
样例输入2
21 0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000 10 77 721 255 541 478 970 369 466 343 541 42 165 16 618 222 592 730 983 338 747
样例输出2
296 150 150 49 89 20 279 183 61 177