34143번 - 힘의 결합 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 180 | 15 | 9 | 14.516% |
문제
빛이 섬 곳곳을 비추기 시작하자, 각 집에 깃든 힘의 흐름이 달라지기 시작했다. 시간에 따라 힘은 이리저리 옮겨졌고, 그 흔적은 조용히 기록되었다.
사람들은 힘의 흐름이 지나간 모든 순간을 되짚으며, 그 안에서 가장 강했던 결합의 순간을 찾아내고자 했다.
그들이 나눈 힘의 흐름을 따라가고, 잃어버린 기록을 되찾아라.
섬의 마을에는 $N$개의 집이 일렬로 놓여 있으며, 집은 왼쪽부터 차례대로 $1$부터 $N$까지의 번호가 붙어 있다.
$0$일째에 집 $i$는 $a_i$만큼의 힘을 지니고 있었다.
시간이 지남에 따라 집들 사이에서 힘이 이동하는 현상이 $M$일 동안 일어났다. 구체적으로, $i$번째 날에는 $x_i$번 마을의 힘이 $v_i$만큼 증가하고, $x_i+1$번 마을의 힘이 $v_i$만큼 감소했다. ($v_i$는 음수일 수도 있다.)
사람들은 시간에 따른 힘의 변화를 격자에 기록했다. 예를 들어, $N=4$, $M=5$, $a=[3,-2,2,-2]$, $x=[3,1,2,1,2]$, $v=[-4,-2,3,2,-4]$인 경우, 각 집의 힘은 시간에 따라 아래와 같이 변한다. 이때 각 행은 날의 번호에 대응되고, 각 열은 집의 번호에 대응된다.
힘의 변화가 일어남에 따라, 몇몇 사람들은 집의 결속력을 강화하고 힘을 분배할 수 있도록 결합을 형성하고자 하였다. 결합이 형성되는 과정은 다음과 같다.
- 결합을 형성할 날짜 $t$와 결합을 이끌 집의 번호 $x$를 정한다. $(0\le t\le M,1\le x\le N)$
- $x$번 집을 포함하는 연속한 집의 구간 $[l,r]$을 고른다. $(1\le l\le x\le r\le N)$
- 결합의 힘은 결합을 이루는 집의 힘의 합과 같다. 단, 각 집의 힘은 결합을 형성한 $t$번째 날의 힘을 기준으로 한다.
- 이때, $P_{tx}$를 $t$와 $x$의 값이 고정되었을 때 만들 수 있는 결합의 힘의 최댓값으로 정의하자.
사람들은 결합을 계획하기 위해 여러 시간대와 여러 집에 대해 가능한 결합의 힘을 비교하고자 하였다. 이 과정에서 $Q$가지의 질문이 등장했는데, 그중 $i$번째 질문은 다음과 같다.
- $s_i\le t\le e_i$, $l_i\le x\le r_i$인 모든 $(t,x)$에 대해, $P_{tx}$의 합이 무엇인가?
결합을 만드는 다양한 가능성을 살펴보고, 각각의 계획이 얼마나 강한지 알아내어 보자.
입력
첫 줄에는 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다.
둘째 줄에는 초기 집의 힘을 나타내는 $N$개의 정수 $a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다.
이후 $M$개의 줄에 걸쳐, 힘의 이동에 관한 두 정수 $x_i$, $v_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 날에 $x_i$번 집의 힘이 $v_i$만큼 증가하고, $x_i+1$번 집의 힘이 $v_i$만큼 감소한다는 의미이다.
이후 $Q$개의 줄에 걸쳐, 각 질문을 나타내는 네 정수 $s_i,e_i,l_i,r_i$가 공백으로 구분되어 주어진다.
출력
$Q$가지 질문 각각에 대해 그 답을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.
제한
- $2\le N\le 10^5$
- $1\le M\le 10^5$
- $1\le Q\le 10^5$
- $-10^9\le a_i\le 10^9$ $(1\le i\le N)$
- $1\le x_i<N$ $(1\le i\le M)$
- $-10^9\le v_i\le 10^9$ $(1\le i\le M)$
- $0\le s_i\le e_i\le M$ $(1\le i\le Q)$
- $1\le l_i\le r_i\le N$ $(1\le i\le Q)$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $N \le 2000, M \le 2000, Q \le 1000, s_i = e_i, l_i = r_i$ $(1 \le i \le Q)$ |
| 2 | 16 | $N \le 2000, M \le 2000, s_i = e_i, l_i = r_i$ $(1 \le i \le Q)$ |
| 3 | 10 | $s_i = e_i, l_i = r_i$ $(1 \le i \le Q)$ |
| 4 | 19 | $s_i = e_i$ $(1 \le i \le Q)$ |
| 5 | 17 | $l_i = r_i$ $(1 \le i \le Q)$ |
| 6 | 30 | 추가 제한 조건이 없다. |
예제 입력 1
4 5 4 3 -2 2 -2 3 -4 1 -2 2 3 1 2 2 -4 1 3 1 2 3 4 3 4 0 2 2 2 0 5 1 4
예제 출력 1
14 6 5 51
예제 입력 2
3 2 9 3 -2 1 1 -3 2 -2 0 0 1 1 0 0 2 2 0 0 3 3 1 1 1 1 1 1 2 2 1 1 3 3 2 2 1 1 2 2 2 2 2 2 3 3
예제 출력 2
3 2 2 2 2 2 2 2 3
출처
Contest > BOJ User Contest > BCF > BCF 2025 VII번
- 문제를 만든 사람: 79brue
- 문제를 검수한 사람: aeren, mjhmjh1104, qwerasdfzxcl, silverwolf
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호