P12624 [ICPC 2025 NAC] Humans vs AI

在人工智能崛起的时代，James 害怕失去工作。因此，当老板要求他评估一个新 AI 模型与人类的表现对比时，他想要尽可能让 AI 看起来表现糟糕。 为了测试 AI，James 进行了 $N$ 次试验，每次试验中人类和 AI 执行相同任务并根据表现评分。之后他将选择这些试验结果的某个非空连续子序列发送给老板，并悄悄删除其余部分。 设 $a_i$ 和 $h_i$ 分别表示第 $i$ 次试验中 AI 和人类的表现。老板通过计算两个总分来评估序列：人类总分和 AI 总分，初始均为 $0$。对于每个 $h_i \geq a_i$ 的试验，老板给人类加 $h_i - a_i$ 分；对于每个 $h_i < a_i$ 的试验，AI 获得 $a_i - h_i$ 分。若人类总分大于等于 AI 总分乘以常数 $k$（考虑人类需要食物、水和工位等因素），老板则判定人类优于 AI。 James 计划通过邮件发送选定的试验结果子序列。但有一个问题：无所不知的 AI 会拦截邮件，并可能选择交换某次试验的 $h_i$ 和 $a_i$ 值（最多交换一次，以免 James 察觉）。 计算有多少个非空连续子序列能保证：即使 AI 交换最多一次试验结果，老板仍会判定人类优于 AI。

第一行输入两个整数 $N$（$1 \leq N \leq 2 \cdot 10^5$）和 $k$（$1 \leq k \leq 100$），分别表示试验次数和 AI 分数乘数。 第二行包含 $N$ 个整数 $h_1, h_2, \ldots, h_N$（$0 \leq h_i \leq 10^6$），表示人类每次试验的表现。 第三行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$（$0 \leq a_i \leq 10^6$），表示 AI 每次试验的表现。

输出满足条件的非空连续子序列数量。

翻译由 DeepSeek V3 完成