涨姿势之区间刷新

TimeLimit:2000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏 | 已有4人收藏了本题
Problem Description

Value_Dragon是一个有钱人。快过年了,所以他准备发红包。但是他发红包的方式很奇葩。他让n个人排成一排。每次选择1-n中的一段区间[l,r]发,给区间中的每一个人一块钱。就这样发了m次红包。发完后他想知道在[1,n]的子区间中有多少个区间满足以下要求

  1. 这个区间得到钱的总数不少于s

  2. 这个区间可以被分成两个不相交的子区间且每个子区间得到的钱的总数不小于w

(注:一个区间的子区间包括自己本身)

防坑提醒,长度为1的区间比如[1,1],是不能被拆成两个子区间的

Input

第一行是一个整数T代表数据的组数。
接下来有T组数据
每组数据开头有四个整数,分别代表n m s w
接下来m行,每行是是两个数l,r代表区间[l,r]的左右端点

其中T<=10

n<=10^6,m<=10^5

0<l<=r<=n

0<=w<=s<10^8

Output

对于每组数据输出一行,代表符合要求的区间个数

SampleInput
4
1 0 0 0

1000000 0 0 0

1000000 1 0 0
1 1000000

10 10 20 14
2 10
5 9
5 5
6 8
2 6
9 10
6 7
6 10
4 5
5 7
SampleOutput
0
499999500000
499999500000
8
Submit
题目统计信息详细
总AC数131
通过人数50
尝试人数54
总提交量268
AC率18.66%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: