4735: 不休陀螺(广东省重点中学信息学邀请赛提高组)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
广东省重点中学信息学邀请赛(GDKOI 2024 day2提高组第二试)
有n张牌组成一个序列，每张牌用一个二元组(ai,bi)表示，意味着打出这张牌需要消耗ai点费用，打出后可以获得bi点费用。
接下来你可以选择一个区间[l,r]将这个区间中的卡取出来作为你的卡组。
开始时你的卡组会按照随机顺序排列并且你有E点费用，然后你会依次从前往后打出这个排列中的卡。
当你打完这个排列中的卡后你的卡组又会重新随机排列然后你再依次打出，直到你无法再打出下一张牌（当前费用小于下一张牌需要消耗的费用）时停止。
如果一个卡组无论在什么情况下都能够无限打下去，我们则称这卡组可以”陀螺无限”。
现在求有多少个区间组成的卡组能够”陀螺无限”。
有n张牌组成一个序列，每张牌用一个二元组(ai,bi)表示，意味着打出这张牌需要消耗ai点费用，打出后可以获得bi点费用。
接下来你可以选择一个区间[l,r]将这个区间中的卡取出来作为你的卡组。
开始时你的卡组会按照随机顺序排列并且你有E点费用，然后你会依次从前往后打出这个排列中的卡。
当你打完这个排列中的卡后你的卡组又会重新随机排列然后你再依次打出，直到你无法再打出下一张牌（当前费用小于下一张牌需要消耗的费用）时停止。
如果一个卡组无论在什么情况下都能够无限打下去，我们则称这卡组可以”陀螺无限”。
现在求有多少个区间组成的卡组能够”陀螺无限”。
输入
第一行输入两个非负整数n,E分别表示卡牌序列长度和初始能量值E(1≤n≤106,0≤E≤109)。
接下来一行n个非负整数ai(0≤ai≤109)表示每张卡牌打出需要消耗的能量。
接下来一行n个非负整数bi(0≤bi≤109)表示每张卡牌打出后能获得的能量。
接下来一行n个非负整数ai(0≤ai≤109)表示每张卡牌打出需要消耗的能量。
接下来一行n个非负整数bi(0≤bi≤109)表示每张卡牌打出后能获得的能量。
输出
输出一行一个整数表示有多少个区间组成的卡组能够” 陀螺无限”。
样例输入 复制
5 10
9 10 10 0 2
8 5 6 2 5样例输出 复制
4提示
数据范围:
本题使用子任务捆绑测试。
对于100%的数据，1≤n≤106,0≤E,ai,bi≤109。
Subtask1(20%):1≤n≤5000。
Subtask2(10%):bi≥ai。
Subtask3(10%):E=0。
Subtask4(10%):0≤ai,bi≤1。
Subtask5(20%):ai×bi=0。
Subtask6(30%):无特殊限制。
本题使用子任务捆绑测试。
对于100%的数据，1≤n≤106,0≤E,ai,bi≤109。
Subtask1(20%):1≤n≤5000。
Subtask2(10%):bi≥ai。
Subtask3(10%):E=0。
Subtask4(10%):0≤ai,bi≤1。
Subtask5(20%):ai×bi=0。
Subtask6(30%):无特殊限制。