← 返回题目列表

AtCoder · dwango2016final_c

C. 无线电塔

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

問題文

dwango 正在建造一座无线电塔。 N 并且所有无线电塔都排成一条直线。 当我们将这条线视为数轴时, 第 i 个无线电塔位于坐标处 它位于 x_i ,高度为 h_i 。由于种种情况,x_i, h_i 均为正偶数。 另外,任何 对于 i≠j , 满足 x_i≠x_j,h_i≠h_j 。

每个无线电塔只能向坐标较大且比自身高的无线电塔发送信息。

二王后君喜欢通过更多无线电塔传递信息。 因此,整数序列 a_1,a_2,...,a_t 和 x_{a_k} < x_{a_{k+1}} 和 h_{a_k} < h_{a_{k+1}} 就是全部 1 ≦ k ≦ t-1 获得的快乐等于此类事物的最大长度。

dwango 为 Niwango 君建造了一座新的无线电塔。 1 我决定打好基础。由于各种情况,无线电塔的坐标和无线电塔的高度都必须是正奇数。

建造无线电塔时,二王后君的幸福感会增加。 有多少对可能的 (座標, 高さ) ?

请注意,坐标是 W 更大的位置和高度 H 由于强磁暴,较高海拔地区没有无线电塔,也无法建造新的无线电塔。


入力

输入是按以下格式从标准输入给出的。

N W H
x_1 h_1
.
.
.
x_N h_N
  • 1 行包含一个整数 N(1 ≦ N ≦ 252525) 和 我讨厌 W(4 ≦ W ≦ 10^9, Wは偶数) 和 我讨厌 H(4 ≦ H ≦ 10^9, Hは偶数) 作为空格分隔符给出。
  • 继续 N 行包含 一个整数,表示第 i 个无线电塔的坐标和高度 x_i(2 ≦ x_i ≦ W-2, x_iは偶数) 和 我讨厌 h_i(2 ≦ h_i ≦ H-2, h_iは偶数) 作为空格分隔符给出。
  • 全部 i(1 ≦ i ≦ N-1) , x_i < x_{i+1} 满意。另外, i ≠ j 如果 如果对满足 h_i ≠ h_j 很满意。 对于

部分点

针对此问题设置了部分分数。

  • N ≦ 52 的数据集给出正确答案,则将其用作部分点。 如果您在数据集中也得到了满足 20 点。
  • N ≦ 2525 的正确答案,则可以将其添加为部分点。 20 点。
  • 如果所有数据集都回答正确,则附加 80 给出积分,总分 120 点。

出力

新的无线电塔位置将增加二王后君的幸福感。 一个整数,表示 (座標, 高さ) 可能对的数量 在 1 行输出。 输出是 32 请注意,它可能不适合位符号整数的范围。 可能的

不要忘记输出末尾的换行符。


入力例1

2 6 6
2 4
4 2

出力例1

6

(座標,高さ) 对是: (1,1),(1,3),(3,1),(3,5),(5,3),(5,5) 的 6 一。


入力例2

4 10 12
2 6
4 2
6 10
8 4

出力例2

16

入力例3

4 10 10
2 6
4 8
6 2
8 4

出力例3

12

入力例4

5 252525252 555255252
25252 52525252
22225252 2225252
55252252 552222222
252522222 52
252525222 555222222

出力例4

7475142133811101