← 返回题目列表

Codeforces · 1753/F

F. 我的世界系列

中文机器翻译题面 查看原题

小米莎去了编程俱乐部,但在那里什么也没解决。这可能看起来很奇怪,但当你发现 Misha 正在拍摄 Minecraft 系列时,一切都会水到渠成......

Misha 受到曼哈顿的启发,因此他在 Minecraft 中建造了一座城市,可以将其想象为一张大小 $$$n \times m$$$ 的桌子。 $$$k$$$ 学生住在一个城市,第 $$$i$$$ 学生住在位于第 $$$x_i$$$ 行和第 $$$y_i$$$ 列交叉点的房子里。此外,每个学生都有一定程度的攻击性$$$w_i$$$。由于城市非常大,Misha 决定将他的系列动作在地域上限制在某个正方形 $$$s$$$ 内,这些正方形的边与坐标轴平行。正方形边长应为从 $$$1$$$ 到 $$$\min(n, m)$$$ 个单元格的整数。

根据剧情,主角会来到城市,不小心掉进广场$$$s$$$。拥有独特程度的进取心$$$0$$$,他将能够展示他的领导才能并组建一支由冷静、温和和进取的学生组成的团队。

为了使组建的团队具有多才多艺和紧密联系,团队中所有学生的攻击性程度必须成对不同,并且必须形成一个连续整数的单段。形式上,如果$$$s$$$方格内存在攻击性程度为$$$l, l+1, \ldots, -1, 1, \ldots, r-1, r$$$的学生,其中$$$l \le 0 \le r$$$,则主英雄将能够组成$$$r-l+1$$$人的团队(当然,他也包含在这个团队中)。

注意,不需要将 $$$s$$$ 方阵的所有学生都带入团队。

Misha 认为团队应该至少由 $$$t$$$ 人组成。这就是为什么他感兴趣的是,表格中有多少个方格,其中主要英雄将能够组建一支至少由 $$$t$$$ 人组成的团队。帮他算一下这个。

输入

第一行包含四个整数 $$$n$$$、$$$m$$$、$$$k$$$ 和 $$$t$$$ ($$$1 \le n, m \le 40\,000$$$, $$$1 \le n \cdot m \le 40\,000$$$, $$$1 \le k \le 10^6$$$, $$$1 \le t \le k + 1$$$) — 分别是表中的行数和列数以及居住在该城市的学生人数。

以下 $$$k$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$w_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le \lvert w_i \rvert \le 10^9$$$) — 第 $$$i$$$ 个学生居住的行数和列数,以及他的攻击性程度。

输出

打印一个整数 - 选择方格 $$$s$$$ 的方法数,使得主要英雄能够组建一支至少由 $$$t$$$ 人组成的团队。

示例

输入 #1

2 2 1 2
1 1 2

输出 #1

0

输入 #2

2 2 2 2
1 1 1
2 2 2

输出 #2

2

输入 #3

2 2 4 2
1 1 1
1 1 -1
1 2 1
2 2 1

输出 #3

4

注意

1. 在第一个示例中,主要英雄将无法在任何方格 $$$s$$$ 中组建超过一个人的团队。 第一个示例的插图。
2. 在第二个示例中,有两种选择正方形 $$$s$$$ 的方法。两者均如下图所示。在其中一个游戏中,主要英雄将能够组建一支攻击性程度为 $$$[0, 1]$$$ 的学生团队,而在另一个游戏中,主角的攻击性程度为 $$$[0, 1, 2]$$$。请注意,无论选择哪个方格,攻击程度为 $$$0$$$ 的主要英雄都将被纳入团队。 第二个例子的插图。
3. 在第三个示例中,有四种方法可以选择正方形$$$s$$$。所有这些都如下图所示。主要英雄将能够组建一支具有攻击性程度的团队:分别为$$$[-1,0,1]$$$、$$$[0,1]$$$、$$$[0,1]$$$、$$$[-1, 0, 1]$$$。 第三个例子的插图。