[R78D]摄影 - 代码源竞赛平台

时空限制

1S/512M

题目描述

当前有 $m$ 个整数时刻 $1,2,3,\cdots m$。摄影师需要在两个整数时刻 $x$ 和 $x+d$ 各拍一张照片，其中 $1\le x<x+d\le m$。

现在一共有 $n$ 个被拍摄对象。第 $i$ 个对象只在整数时刻 $l_i,l_i+1,\ldots,r_i$ 出现，价值为 $w_i$。如果它恰好出现在两张照片中的一张，就为总分贡献 $w_i$；如果它在两张照片中都出现，或都没有出现，则贡献 $0$。

选择整数 $x$，使总分最大。求最高总分，以及有多少个合法的 $x$ 能达到这一分数。

格式

输入格式

第一行包含三个整数 $n,m,d$，分别表示对象数量、可拍摄的最大时刻和两张照片的时间间隔。

接下来 $n$ 行，第 $i$ 行包含三个整数 $l_i,r_i,w_i$，分别表示第 $i$ 个对象出现的起止时刻和价值。

输出格式

输出一行，包含两个整数，依次表示最高总分和达到最高总分的合法整数 $x$ 的数量。

样例

样例输入 #1

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

样例输出 #1

7 1

样例解释 #1

取 $x=3$ 时，拍摄时刻为 $3$ 和 $5$。第 $1$ 个对象只出现在第一张照片中，贡献 $4$ 分；第 $2$ 个对象在两张照片中都出现，贡献 $0$ 分；第 $3$ 个对象只出现在第二张照片中，贡献 $3$ 分。总分为 $7$，且只有这一个合法的 $x$ 能达到最高分。

样例输入 #2

1 6 2
1 3 1

样例输出 #2

1 2

样例解释 #2

取 $x=2$ 或 $x=3$ 时，该对象都恰好出现在一张照片中，总分为 $1$。其余合法的 $x$ 得分为 $0$。

样例输入 #3

1 2 1
1 2 1000000000

样例输出 #3

0 1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$m\le$
$1$	$20$	$1000$	$1000$
$2$	$30$		$10^{18}$
$3$	$20$	$2\times 10^5$	$2\times 10^5$
$4$	$30$		$10^{18}$

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$2\le m\le 10^{18}$，$1\le d<m$，$1\le l_i\le r_i\le m$，$1\le w_i\le 10^{9}$。