QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 5171. 理论出线

Statistics

题目描述

寒冬将至,FIS滑雪世界杯正在火热进行,选手们将参加本赛季中的举办的若干场比赛,以获取积分获得奥运会资格。作为滑雪比赛的忠实观众,小 Z 自然不打算错过任何一场比赛。

在小 Z 的世界中,世界杯的赛制与现实有较大的不同:本赛季共有 $m$ 个比赛日,将依次举行 $m$ 场比赛,有 $n$ 名选手参加,第 $i$ 名选手在之前的赛季中已经有了 $w_i$ 的积分,由于身体原因,会在第 $l_i$ 个比赛日抵达比赛现场,第 $r_i$ 个比赛日离开,参加第 $l_i\sim r_i$ 场比赛。每场比赛如果有至少一人参加,就会在这些选手间进行竞争,选出唯一的胜者,胜者将获得 $1$ 点积分。

特别地,为了保证公平,不让一些选手参与过多的比赛,对于任意两名选手 $i,j$,如果 $i$ 比 $j$ 先抵达现场,则不能比 $j$ 更晚离开。即 $\forall 1\le i,j\le n$,$l_i < l_j$ 则 $r_i\le r_j$。

不幸的是,小 Z 最喜欢的一名选手 UFT 由于身体原因将缺席本赛季所有的比赛(UFT 不算在那 $n$ 名选手中,可以看作共有 $n+1$ 名选手进行排名),小 Z 想知道 UFT 还有没有出线晋级奥运会的理论可能。UFT 在以往的赛季中获得了积分 $v$,由于不确定奥运会名额的数量,小 Z 想向你询问本赛季结束后所有的不同积分情况中,UFT 的排名最高为多少(定义一名选手的排名为分数比他高的选手数量 $+1$),设这个最小值为 $mn$,你需要输出 $n+1-mn$ 的大小(即分数不高于 $v$ 的选手数量)。由于积分相同需要考虑选手历史战绩,所以小 Z 还想要额外知道:所以可以达到的,满足 UFT 排名为 $mn$ 的不同最终积分情况中,积分不高于 UFT 的选手集合有多少种不同的可能。答案关于 $10^9+7$ 取模。

输入格式

第一行四个整数 $n,m,v,tp$。$n,m,v$ 参见题目描述, $tp$ 为询问类型满足 $tp\in \{0,1\}$,当 $tp=0$ 时你只需要输出第一问答案,$tp=1$ 时则需要输出两问的答案。

接下来 $n$ 行,第 $i$ 行三个正整数 $w_i,l_i,r_i$。

输出格式

一行一个或两个整数表示答案,答案之间用空格隔开。

样例数据

input

7 7 2 1
1 1 1
1 2 3
2 3 4
1 4 4
2 4 5
1 5 6
2 5 7

output

5 2

样例解释

可能 $1$:比赛胜者依次为 $1,2,3,3,7,7,7$,选手 $1,2,4,5,6$ 分数 $\le 2$。

可能 $2$:比赛胜者依次为 $1,2,2,4,7,7,7$,选手 $1,3,4,5,6$ 分数 $\le 2$。

数据规模与约定

对于所有测试数据,有 $1\le n,m\le 2\times 10^5,0\le w_i,v\le 1\times 10^9,1\le l_i\le r_i\le m,0\le tp\le 1$。 且 $\forall 1\le i,j\le n,i\not =j$,若 $l_i< l_j$ 则 $r_i\le r_j$。

subtask $1$($5\%$): $n,m\le 8$。

subtask $2$($5\%$): $n,m\le 15$。

subtask $3$($20\%$): $n,m\le 20$。

subtask $4$($10\%$): $n,m\le 2000,tp=0$。

subtask $5$($20\%$): $tp=0$。

subtask $6$($20\%$): $n,m\le 2000$。

subtask $7$($20\%$): 无特殊限制。

时间限制:$1\text{s}$

空间限制:$256\text{MB}$