24838번 - 배열 구간합 놀이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (하단 참고) | 512 MB | 101 | 37 | 27 | 39.706% |
문제
Alice는 정수 배열을 이용한 구간합 놀이를 즐겨하는데, 아래와 같은 순서로 게임을 진행한다.
- 먼저, 길이 $n$인 정수 배열 $A$를 만든다. $A$의 원소가 $A[1]$, $\dots$, $A[n]$이라 했을 때 이 $n$개의 값은 모두 달라야 한다.
- 다음으로, 배열 $A$의 구간을 나타내는 $m$개의 정수 쌍 $(x[1], y[1])$, $\dots$, $(x[m], y[m])$을 고른다. 이 때 $1 ≤ x[i] ≤ y[i] ≤ n$ 을 만족해야한다.
- 배열 $A$와 $x$, $y$를 이용하여 구간합 $S(A, x, y)$을 다음과 같이 정의한다: $S(A, x, y) := \sum_{1 \le j \le m} ( \sum_{x[j] \le i \le y[j]} A[i] )$
- 이 게임의 목표는 배열 $A$의 원소를 임의로 재배열하여 $S(A, x, y)$값을 최대로 만드는 것이다. $A$의 원소가 $n$개이므로 총 $n!$ 가지의 방법으로 $A$의 원소를 재배열할 수 있다.
예를 들어, $n = 3$, $m = 2$, $A = [10, 100, 1000]$ 이고 $x = [1, 2]$, $y = [2, 2]$라 하자. $n = 3$ 이므로 $A$의 원소를 재배열하여 얻을 수 있는 배열은 총 여섯 종류가 있다. 원래의 배열 $A$와 구분하기 위해 이를 배열 $B$라 하자.
- $B = [10, 100, 1000]$ 일 때, $S(B, x, y) = (10 + 100) + (100) = 210$.
- $B = [10, 1000, 100]$ 일 때, $S(B, x, y) = (10 + 1000) + (1000) = 2010$.
- $B = [100, 10, 1000]$ 일 때, $S(B, x, y) = (100 + 10) + (10) = 120$.
- $B = [100, 1000, 10]$ 일 때, $S(B, x, y) = (100 + 1000) + (1000) = 2100$.
- $B = [1000, 10, 100]$ 일 때, $S(B, x, y) = (1000 + 10) + (10) = 1020$.
- $B = [1000, 100, 10]$ 일 때, $S(B, x, y) = (1000 + 100) + (100) = 1200$.
이 경우 $S(A, x, y)$의 최댓값은 $2100$이며, 네 번째 경우인 $B = [100, 1000, 10]$를 통해 얻을 수 있다.
다른 예로, $n = 2$, $m = 1$, $A = [20, 22]$ 이고 $x = [1]$, $y = [2]$라 하자. $n = 2$ 이므로 $A$의 원소를 재배열하여 얻을 수 있는 배열은 총 두 종류가 있다. 원래의 배열 $A$와 구분하기 위해 이를 배열 $B$라 하자.
- $B = [20, 22]$ 일 때, $S(B, x, y) = (20 + 22) = 42$.
- $B = [22, 20]$ 일 때, $S(B, x, y) = (22 + 20) = 42$.
이 경우 $S(A, x, y)$의 최댓값은 $42$이며, 두 가지 다른 방법을 통해 얻을 수 있다.
$A$, $x$, $y$가 주어졌을 때 Alice가 $A$의 원소를 재배열하여 달성할 수 있는 $S(A, x, y)$의 최댓값을 구하고, 몇 가지 다른 방법으로 최댓값을 달성할 수 있는지 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 입력 첫 줄에 $n$, $m$이 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$의 원소 $n$개가 공백으로 구분되어 주어진다. 다음 $m$줄에 걸쳐 각 줄에 두 개의 정수 $x[i]$와 $y[i]$가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.
제한
- $1 ≤ T ≤ 10$
- $1 ≤ n ≤ 50\,000$
- $1 ≤ m ≤ 200\,000$
- $1 ≤ A$의 원소 $≤ 10^8$
- 배열 $A$의 원소는 고유하다
- $1 ≤ i ≤ m$인 정수 $i$에 대하여 $1 ≤ x[i] ≤ y[i] ≤ n$
예제 입력 1
6 3 2 10 100 1000 1 2 2 2 2 1 20 22 1 2 5 3 1 3 5 7 9 1 2 2 3 3 4 6 1 1 2 3 100 200 300 1 2 7 7 100000000 99999999 99999998 99999997 99999996 99999995 99999994 1 7 2 7 3 7 4 7 5 7 6 7 7 7 13 1 1 2 3 4 5 6 7 8 9 10 11 12 13 1 13
예제 출력 1
2100 1 42 2 40 4 500 48 2799999944 1 91 227020758
- 예제 1-2: 본문에서 다루었다
- 예제 3-4: 추가 설명 없음
- 예제 5: 최댓값은 32-bit integer 범위를 넘어감에 주의하자.
- 예제 6: 최댓값을 달성할 수 있는 방법의 수는 매우 커질 수 있으므로 ($10^9+7$)로 나눈 나머지를 출력해야한다.
시간 제한
- Java 8: 3 초
- Python 3: 4 초
- PyPy3: 4 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호