#2144. Peru

    ID: 2144 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1269来源:qoj.ac数据:公开样例线段树平衡树

Peru

Peru

题目描述

RMI 2020, Day 1 Online, 3.12.2020 Problem Peru C header: peru.h C++ header: peru.h This morning, Roxy found N beetles on her desk. These beetles are numbered from 0 to N −1 and each beetle i has a strength Si. Roxy wants to crush the beetles so she can do her math homework. In order to do this, she bought a special glove which she can use to hit a contiguous subsequence of K beetles. If Roxy makes an effort E, then those beetles whose strength Si is smaller than or equal to E will be crushed, while all others will remain unharmed. The crushed beetles maintain their positions on the desk. Roxy can use the glove as many times as she wants. Roxy wants to know if you can compute the minimum total effort needed to crush the first i beetles for each 1 ≤i ≤N. Because there are too many numbers, Roxy agreed you should give her the result of the following expression: X0 · 23N−1 + X1 · 23N−2 + . . . + XN−1 modulo 109 + 7, where Xi represents the minimum total effort to crush the first i + 1 beetles. Implementation details The contestant must implement the following function: int ∗S ) ; int solve ( int N, int K, This function will be called exactly once and must return the result of the above expression modulo 109 + 7. The parameters of this function are N (the number of beetles), K (the length of the contiguous subsequences she can hit with the glove) and S (an array of length N, where Si represents the strength of beetle i). Constraints • 1 ≤N ≤2 500 000 • 1 ≤K ≤N • 1 ≤Si ≤2 000 000 000 Subtask 1 (18 points) • 1 ≤N ≤2 000 Subtask 2 (31 points) • 1 ≤N ≤400 000 Subtask 3 (51 points) • No additional constraints. Example input output 8 3 720026253 3 2 9 8 7 11 3 4 The array X is {3, 3, 9, 12, 12, 20, 23, 23}. 1

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

8 3
3 2 9 8 7 11 3 4
720026253