No.1673 Lamps on a line
レベル :
/ AI推定難易度 : 163
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 264
作問者 :
stoq
/ テスター :
akakimidori
ekaraage
タグ : / 解いたユーザー数 264
作問者 :
stoq
/ テスター :
akakimidori
ekaraage
問題文最終更新日: 2021-09-10 23:41:44
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 313
(順位表)
の他の問題:
Problem Statement
$N$ lamps are arranged in a row. Initially, all the lamps are off.
You perform the following operation $Q$ times.
- In the $i$-th operation, toggle the ON/OFF state of the $L_i,L_i+1,\dots,R_i$-th lamps from the left. That is, lamps that are off are turned on, and lamps that are on are turned off.
Input
$N\ Q$ $L_1\ R_1$ $\vdots$ $L_Q\ R_Q$
- All inputs are integers.
- $1 \leq N \leq 5 \times 10^5$
- $1 \leq Q \leq 10^5$
- $1 \leq L_i \leq R_i \leq N$
- $R_i - L_i \leq 10 \ (1 \leq i \leq Q)$
Output
For each $i=1,2,\dots,Q$, output the number of lamps that are on after the $i$-th operation, separated by newlines.
Sample
Sample 1
Input
5 3 1 5 1 3 2 4
Output
5 2 3
Representing off as 0 and on as 1, the lamps change as $00000 \rightarrow 11111 \rightarrow 00011 \rightarrow 01101$.
Sample 2
Input
1 2 1 1 1 1
Output
1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。