시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 1024 MB | 64 | 30 | 12 | 42.857% |
이 문제는 인터랙티브 문제가 아닙니다.
리프는 코드포스 레드를 가기 위해 구사과에게 특별 훈련을 받고 있다. 구사과는 리프에게 수열 $A$를 주고, 자신이 생각하는 수열 위의 구간 $I=[a, b]$ 내의 수들의 값을 맞춰 보라고 했다.
리프는 구사과에게 아래와 같은 종류의 질문을 할 수 있다.
원래는 리프가 구사과에게 적은 횟수의 질문을 해서 $[a, b]$ 내의 수들의 값을 맞춰야 했겠지만, 구사과가 깜박하고 질문 횟수 제한을 거는 것을 잊어버렸다. 리프는 모든 구간에 대해 위와 같은 질문을 하고 구사과가 낸 문제를 쉽게 풀어 내었다.
구사과는 이렇게 된 이상, 리프에게 아래와 같은 문제를 $Q$개 낸 뒤 빠르게 풀라고 했다. 리프를 도와 구사과가 낸 문제를 빠르게 푸는 프로그램을 작성해 보자.
첫 줄에는 구사과가 만든 수열의 길이 $N$과 구사과의 질문의 횟수 $Q$가 주어진다.
둘째 줄에는 수열 $A$의 각 원소가 $A_1, A_2, \cdots, A_N$의 형태로 주어진다.
셋째 줄부터 $Q+2$번 줄까지 $Q$개의 줄에는 구사과의 $Q$개의 질문을 나타내는 두 정수 $l_i$ $r_i$가 주어진다.
$Q$개의 질문에 대해 답을 $MOD$로 나눈 나머지를 한 줄에 하나씩 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $1 \le N \le 100$, $1 \le Q \le 50$ |
2 | 15 | $1 \le N \le 1000$, $1 \le Q \le 50$ |
3 | 22 | $1 \le N \le 3000$, $1 \le Q \le 3000$ |
4 | 23 | $Q = 1$ |
5 | 20 | $1 \le N \le 10^5$, $1 \le Q \le 10^5$ |
6 | 10 | 추가 제한 조건이 없다. |
5 5 1 2 3 1 2 1 5 1 2 2 4 3 3 4 5
18 12 10 3 12
1 1 20 1 1
1
10 5 2 2 2 2 2 2 2 2 2 2 1 10 1 1 3 8 10 10 2 5
220 55 200 55 164
Contest > BOJ User Contest > Orange Cup > Orange Cup G번