시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 210 | 57 | 45 | 25.862% |
Yuto와 Platina가 Non-Decreasing Subarray Game을 하려고 한다. 게임은 길이 N의 배열 A에서 진행된다.
Yuto가 먼저 정수 하나를 부르고, 그걸 듣고 Platina가 정수를 하나 부른다. 이때 얻게 되는 점수는 둘이 부른 수 중 크지 않은 수를 a, 작지 않은 수를 b라고 했을 때, a ≤ i ≤ j ≤ b이며 구간 [i, j]가 Non-Decreasing Subarray를 이루는 서로 다른 (i, j) 쌍의 개수이다.
이때 [i, j]가 Non-Decreasing Subarray 를 이룬다는 것은 주어진 배열에서 i ≤ x ≤ y ≤ j이면, Ax ≤ Ay라는 것을 뜻한다.
Yuto는 점수가 최소화되기를 원하며, Platina는 점수가 최대화되기를 원한다. 이 게임은 너무나도 재미있어서 부를 수 있는 수의 제한을 바꿔가면서 게임을 T판 진행하려고 한다! 각 판마다 둘이 얻게 될 점수를 구하여라.
첫째 줄에는 두 양의 정수 N과 T가 주어진다.
둘째 줄에는 배열의 값 A1, A2, A3, ..., AN이 주어진다.
셋째 줄부터 T+2번째 줄까지는 i번째 게임에서 설정한 수의 제한 Li, Ri가 양의 정수로 주어진다. 이는 그 게임에서 두 사람이 부를 수 있는 수가 Li 이상 Ri 이하라는 것을 뜻한다.
각 게임별로 두 사람이 얻게 될 점수를 각 줄에 걸쳐 출력한다.
8 5 7 10 3 1 9 5 5 2 1 5 2 2 5 8 1 8 3 5
4 1 4 7 3
Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup H번
Camp > Petrozavodsk Programming Camp > Summer 2020 > Day 6: Korean Contest D번