34114번 - Uiro 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 2048 MB | 116 | 10 | 9 | 8.257% |
문제
Aoi has $N$ cards numbered from $1$ to $N$. Each card has a positive integer written on it. The integer written on the card $i$ ($1 ≤ i ≤ N$) is $A_i$.
Aoi is going to play a game $Q$ times using the cards and a blackboard. The $j$-th game ($1 ≤ j ≤ Q$) she plays consists of the following steps.
- Write $0$ on the blackboard.
- Arrange the cards $L_j , L_j + 1, \dots , R_j$ on the desk from left to right in this order.
- Perform the following operation for $R_j − L_j + 1$ times. The $k$-th operation ($1 ≤ k ≤ R_j − L_j + 1$) is as follows.
- Let $x$ be the current integer written on the blackboard, and let $y$ be the integer written on the $k$-th card from the left on the desk. Erase $x$ from the blackboard, and write either $x + y$ or $x − y$ instead. If $x − y$ is chosen, Aoi eats one piece of uiro, a traditional Japanese sweet.
- However, writing an integer strictly less than $0$ is not allowed.
For each game, you want to know the maximum number of uiro pieces Aoi can eat.
Given the information about cards and games, write a program that, for each game, calculates the maximum number of uiro pieces Aoi can eat.
입력
Read the following data from the standard input.
$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$
출력
Write $Q$ lines to the standard output. In the $j$-th line ($1 ≤ j ≤ Q$), output the maximum number of uiro pieces Aoi can eat in the $j$-th game.
제한
- $1 ≤ N ≤ 200\, 000$.
- $1 ≤ A_i ≤ 100$ ($1 ≤ i ≤ N$).
- $1 ≤ Q ≤ 200\, 000$.
- $1 ≤ L_j ≤ R_j ≤ N$ ($1 ≤ j ≤ Q$).
- Given values are all integers.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $N ≤ 20$, $Q ≤ 20$. |
| 2 | 5 | $N ≤ 300$, $Q ≤ 20$. |
| 3 | 7 | $N ≤ 5\,000$, $Q ≤ 20$. |
| 4 | 15 | $Q ≤ 20$. |
| 5 | 21 | $A_i ≤ 2$ ($1 ≤ i ≤ N$). |
| 6 | 29 | $A_i ≤ 20$ ($1 ≤ i ≤ N$). |
| 7 | 20 | No additional constraints. |
예제 입력 1
5 3 4 7 2 8 2 1 3 4 4
예제 출력 1
1 0
One possible sequence of actions in the first game is as follows:
- Write $0$ on the blackboard.
- Arrange the cards $1$, $2$, $3$ on the desk from left to right in this order.
- The current integer written on the blackboard is $0$, and the integer written on the first card from the left on the desk is $3$. Erase $0$ from the blackboard and write $3$ instead.
- The current integer written on the blackboard is $3$, and the integer written on the second card from the left on the desk is $4$. Erase $3$ from the blackboard and write $7$ instead.
- The current integer written on the blackboard is $7$, and the integer written on the third card from the left on the desk is $7$. Erase $7$ from the blackboard and write $0$ instead. Aoi eats one piece of uiro.
In this case, the number of uiro pieces Aoi eats in the first game is $1$. It can be proven that the number of uiro pieces Aoi eats in the first game does not exceed $1$. Therefore, you should output $1$.
One possible sequence of actions in the second game is as follows:
- Write $0$ on the blackboard.
- Arrange the card $4$ on the desk.
- The current integer written on the blackboard is $0$, and the integer written on the first card from the left on the desk is $2$. Erase $0$ from the blackboard and write $2$ instead.
In this case, the number of uiro pieces Aoi eats in the second game is $0$. It can be proven that the number of uiro pieces Aoi eats in the second game does not exceed $0$. Therefore, you should output $0$.
This sample input satisfies the constraints of subtasks 1, 2, 3, 4, 6, and 7.
예제 입력 2
14 1 2 2 1 2 1 1 2 1 2 2 1 1 1 5 1 2 1 14 5 11 3 12 4 7
예제 출력 2
0 8 4 6 2
One possible sequence of actions in the first game is as follows:
- Write $0$ on the blackboard.
- Arrange the cards $1$, $2$ on the desk from left to right in this order.
- The current integer written on the blackboard is $0$, and the integer written on the first card from the left on the desk is $1$. Erase $0$ from the blackboard and write $1$ instead.
- The current integer written on the blackboard is $1$, and the integer written on the second card from the left on the desk is $2$. Erase $1$ from the blackboard and write $3$ instead.
In this case, the number of uiro pieces Aoi eats in the first game is $0$. It can be proven that the number of uiro pieces Aoi eats in the first game does not exceed $0$. Therefore, you should output $0$.
This sample input satisfies the constraints of all subtasks.
예제 입력 3
8 16 23 45 76 43 97 12 43 7 1 8 3 7 2 7 4 5 5 8 2 6 3 5
예제 출력 3
3 2 2 1 2 2 1
This sample input satisfies the constraints of subtasks 1, 2, 3, 4, and 7.
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호