[GDKOI2024 提高组] 不休陀螺

Luogu
IDLGP10083
Time2000ms
Memory512MB
DifficultyP5
2024广东O2优化
有 $n$ 张牌组成一个序列,每张牌用一个二元组 $(a_i , b_i)$ 表示,意味着打出这张牌需要消耗 $a_i$ 点费用,打出后可以获得 $b_i$ 点费用。 接下来你可以选择一个区间 $[l, r]$ 将这个区间中的卡取出来作为你的卡组。 开始时你的卡组会按照随机顺序排列并且你有 $E$ 点费用,然后你会依次从前往后打出这个排列中的卡。 当你打完这个排列中的卡后你的卡组又会重新随机排列然后你再依次打出,直到你无法再打出下一张牌(当前费用小于下一张牌需要消耗的费用)时停止。 如果一个卡组无论在什么情况下都能够无限打下去,我们则称这卡组可以“陀螺无限”。 现在求有多少个区间组成的卡组能够“陀螺无限”。 ## Input 第一行输入两个非负整数 $n, E$ 分别表示卡牌序列长度和初始能量值 $E(1 \leq n \leq 10^6, 0 \leq E \leq 10^9)$。 接下来一行 $n$ 个非负整数 $a_i(0 \leq a_i \leq 10^9)$ 表示每张卡牌打出需要消耗的能量。 接下来一行 $n$ 个非负整数 $b_i(0 \leq b_i \leq 10^9)$ 表示每张卡牌打出后能获得的能量。 ## Output 输出一行一个整数表示有多少个区间组成的卡组能够“陀螺无限”。 [samples] ## Note **本题使用子任务捆绑测试。** 对于 $100\%$ 的数据,$1 \leq n \leq 10^6$,$0 \leq E, a_i, b_i \leq 10^9$。 - Subtask 1(20%):$1 \leq n \leq 5000$。 - Subtask 2(10%):$b_i \geq a_i$。 - Subtask 3(10%):$E = 0$。 - Subtask 4(10%):$0 \leq a_i, b_i \leq 1$。 - Subtask 5(20%):$a_i \times b_i = 0$。 - Subtask 6(30%):无特殊限制
Samples
Input #1
5 10
9 10 10 0 2
8 5 6 2 5
Output #1
4
Input #2
5 10
8 1 6 4 10
7 6 1 8 5
Output #2
5
API Response (JSON)
{
  "problem": {
    "name": "[GDKOI2024 提高组] 不休陀螺",
    "description": {
      "content": "有 $n$ 张牌组成一个序列,每张牌用一个二元组 $(a_i , b_i)$ 表示,意味着打出这张牌需要消耗 $a_i$ 点费用,打出后可以获得 $b_i$ 点费用。 接下来你可以选择一个区间 $[l, r]$ 将这个区间中的卡取出来作为你的卡组。 开始时你的卡组会按照随机顺序排列并且你有 $E$ 点费用,然后你会依次从前往后打出这个排列中的卡。 当你打完这个排列中的卡后你的卡组又会重新随机",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10083"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 张牌组成一个序列,每张牌用一个二元组 $(a_i\n, b_i)$ 表示,意味着打出这张牌需要消耗 $a_i$ 点费用,打出后可以获得 $b_i$ 点费用。\n\n接下来你可以选择一个区间 $[l, r]$ 将这个区间中的卡取出来作为你的卡组。\n\n开始时你的卡组会按照随机顺序排列并且你有 $E$ 点费用,然后你会依次从前往后打出这个排列中的卡。\n\n当你打完这个排列中的卡后你的卡组又会重新随机...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments