#P12939. [AGC015E] Mr.Aoki Incubator

    ID: 12123 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-离散化前后缀最值区间覆盖计数 DP前缀和优化 DP树状数组

[AGC015E] Mr.Aoki Incubator

题目描述

在数轴上有 NN 个高桥君排成一排,他们的编号从 11 到 NN。第 ii 个高桥君在时刻 00 时位于位置 XiX_i,并以速度 ViV_i 向正方向开始行走。

「けすぬ君」可以在时刻 00 时,从所有高桥君中选择若干人,将他们变成青木君。即使高桥君变成青木君,他们的行走速度也不会改变。之后,如果某一时刻某个高桥君和青木君位于同一位置,这个高桥君也会变成青木君。

在 2N2^N 种初始将高桥君变为青木君的方法中,有多少种方法能使得在足够长时间后,所有高桥君全部都变为青木君?请将这个数对 109+710^9+7 取模后输出。

输入格式

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

NN
X1X_1 V1V_1
X2X_2 V2V_2
⋮\vdots
XNX_N VNV_N

输出格式

输出一个整数,表示在足够长时间后所有高桥君都变成青木君的方法数,对 109+710^9+7 取模。

输入输出样例 #1

输入 #1

3
2 5
6 1
3 7

输出 #1

6

输入输出样例 #2

输入 #2

4
3 7
2 9
8 16
10 8

输出 #2

9

说明/提示

限制条件

  • 1≤N≤2000001 \leq N \leq 200000
  • 1≤Xi,Vi≤109 (1≤i≤N)1 \leq X_i, V_i \leq 10^9 \ (1 \leq i \leq N)
  • XiX_i 互不相同
  • ViV_i 互不相同

样例解释 1

当けすぬ君选择第 (2),(3),(1,2),(1,3),(2,3),(1,2,3)(2), (3), (1,2), (1,3), (2,3), (1,2,3) 个高桥君变成青木君时,经过足够长时间后,所有高桥君都会变成青木君。