#P12624. [NAC 2025] Humans vs AI

[NAC 2025] Humans vs AI

题目描述

In the world of rising AI, James is scared of losing his job. So, when his boss asks him to evaluate a new AI model to see how well it performs compared to humans, he wants to make it look as bad as possible.

To test the AI, James conducts a sequence of NN trials where a human and an AI are given the same task and then scored based on their performance on the task. He is then going to send the results of some non-empty contiguous subsequence of these trials to his boss and quietly delete the rest.

Let aia_i and hih_i be the performance of the AI and human on trial ii, respectively. James's boss evaluates the AI on a sequence of trials by calculating two total scores: one for the humans, and one for the AI. Both scores are initially 00. For each trial ii where hiaih_i \geq a_i, the boss awards the humans hiaih_i-a_i points. For each trial where hi<aih_i < a_i, the AI earns aihia_i-h_i points. If the humans' total score is greater than or equal to the AI's total score times some constant kk (to account for humans needing food, water, and a desk), James's boss declares that the humans outperform the AI.

James plans to send his chosen subsequence of test results through email to his boss. There is, however, one complication: since AI is already all-knowing and all-pervasive, it intercepts this email and may swap the value of hih_i and aia_i for one trial ii of its choice. (It doesn't want to swap more than one trial result---James might notice!)

Count how many non-empty contiguous subsequences of trial results James could send his boss with the guarantee that humans will be declared to outperform the AI, even if the AI swaps the result of up to one trial.

输入格式

The first line of input contains two space-separate integers: NN (1N21051 \leq N \leq 2 \cdot 10^5), the total number of trials James conducted, and kk (1k1001 \leq k \leq 100), the multiplier James's boss will apply to the AI's total score to determine whether humans outperform AI.

The second line contains NN space-separated integers h1,h2,,hNh_1, h_2, \ldots, h_N (0hi1060 \leq h_i \leq 10^6), the performance of the humans on each of the NN trials.

The third line contains NN space-separated integers a1,a2,,aNa_1, a_2, \ldots, a_N (0ai1060 \leq a_i \leq 10^6), the performance of the AI on the NN trials.

输出格式

Print the number of non-empty contiguous trial subsequences for which James's boss would declare that humans outperform AI, even if the AI swaps the result of up to one trial.

10 2
3 5 7 6 8 6 4 5 2 6
2 4 6 5 4 3 3 6 3 4
4
7 1
4 3 2 1 7 6 5
4 2 3 1 7 6 5
11