luogu#P11239. 「KTSC 2024 R2」跳跃游戏

「KTSC 2024 R2」跳跃游戏

题目背景

请使用 C++17 或 C++20 提交

你需要在程序开头加入如下代码:

#include<vector>
long long play_game(long long N, int Q, long long K, std::vector<long long> L, std::vector<long long> R);

题目描述

题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「점프 게임

KOI 公司推出的跳跃游戏是一款通过多次跳跃穿越 NN 个踏板的游戏。具体来说,游戏中有 NN 个踏板按顺序排列在一条直线上,每个踏板从左到右依次编号为 0,1,,N10, 1, \ldots, N-1。游戏开始时,主角站在最左边的 00 号踏板上,初始得分为 00

对于每个 ii (0iN1)(0 \leq i \leq N-1),主角可以选择走一步或跳跃。如果选择走一步,主角将移动到 i+1i+1 号踏板,得分不变。如果选择跳跃,主角将移动到 i+Ki+K 号踏板,得分增加 A[i]A[i]。其中 KK 是预先设定的常数。游戏在主角到达 N1N-1 号踏板的右侧时成功结束。也就是说,主角到达编号为 N,N+1,N, N+1, \ldots 的踏板时,游戏结束——这些编号大于等于 NN 的踏板实际上不存在,但表示主角已经越过了 N1N-1 号踏板。游戏的目标是通过合理控制主角的行动,使得分最大化并成功结束游戏。

喜欢网络直播的尚赫偶尔会玩 KOI 公司的跳跃游戏。虽然他自己玩得很开心,但观众们却反应平平。跳跃游戏不受欢迎的原因在于游戏非常困难且枯燥。首先,这款游戏的踏板数量可以多达 101210^{12} 个。其次,即使是 KOI 公司的优秀开发者也无法设计出如此多的踏板,因此他们采用了一种相对简单的方法来生成每个踏板。开发者们最初将所有 A[i]A[i] 设置为 00,然后进行 QQ 次操作:对于每个 jj (0jQ1)(0 \leq j \leq Q-1),他们选择一个区间 0L[j]R[j]N10 \leq L[j] \leq R[j] \leq N-1,将 A[L[j]],A[L[j]+1],A[L[j]+2],,A[R[j]]A[L[j]], A[L[j]+1], A[L[j]+2], \ldots, A[R[j]] 的值增加 11。所有操作完成后的数组 AA 就是游戏中每个踏板跳跃时获得的得分。

你是一名制作计算机科学视频的创作者,决定制作一个关于如何以最高得分完成 KOI 公司的跳跃游戏的视频。你认为这个视频会在尚赫的观众中大受欢迎,但你担心游戏规模太大,难以找到高效的算法。克服所有困难,在给定的 5 小时内成为这款游戏的高手吧!

你需要实现以下函数:

long long play_game(long long N, int Q, long long K, std::vector<long long> L, std::vector<long long> R);
  • N:游戏中存在的踏板数量。
  • Q:开发者执行的操作次数。
  • K:跳跃后到达的下一个踏板的编号。
  • L, R:大小为 QQ 的整数数组。
  • 该函数返回一个整数,表示跳跃游戏结束时可以获得的最高得分。
  • 该函数在每个测试点中只会被调用一次。

输入格式

示例评测程序按以下格式读取输入:

  • 11 行:NQKN\,Q\,K
  • 2+i2+i (0iQ1)(0 \leq i \leq Q-1) 行:L[i]R[i]L[i]\,R[i]

输出格式

示例评测程序按以下格式输出:

  • 11 行:play_game 返回的值
3 5 2
0 2
0 2
1 1
1 1
1 1
5
250 8 50
0 200
40 140
49 49
50 150
100 190
149 199
199 199
75 249
17
250 8 49
0 200
40 140
49 49
50 150
100 190
149 199
199 199
75 249
19
100 6 50
0 99
0 70
0 10
20 30
40 50
60 70
6
1000000000000 2 1
0 999999999999
0 999999999999
2000000000000

提示

对于所有输入数据,满足:

  • 1N10121 \leq N \leq 10^{12}
  • 1Q2.51051 \leq Q \leq 2.5\cdot 10^5
  • 1KN1 \leq K \leq N
  • 对于所有 jj (0jQ1)(0 \leq j \leq Q-1)0L[j]R[j]N10 \leq L[j] \leq R[j] \leq N-1

详细子任务附加限制及分值如下表所示。

子任务 分值 附加限制
11 66 N2.5105N \leq 2.5\cdot 10^5
22 K=1K=1
33 1313 2KN2 K \geq N
44 1515 5KN5 K \geq N
55 1616 Q500Q \leq 500
66 77 Q5000Q \leq 5000
77 4141 无附加限制