[AGC015E] Mr.Aoki Incubator
题意翻译
题目大意
数轴上有$N$个点,每个点初始时在位置$X_i$,以$V_i$的速度向数轴正方向前进
初始时刻,你可以选择一些点为其染色,之后的行走过程中,染色的点会将其碰到的所有点都染上色,之后被染上色的点亦是如此
在所有$2^N$种初始染色方案中,问有多少种初始染色方案,能使得最终所有的点都被染色?答案对$10^9+7$取模
题目描述
[problemUrl]: https://atcoder.jp/contests/agc015/tasks/agc015_e
数直線上に $ N $ 人の高橋君が並んでおり、$ 1 $ から $ N $ までの番号がついています。 $ i $ 人目の高橋君は、時刻 $ 0 $ に位置 $ X_i $ にいて、速度 $ V_i $ で正の方向に歩き始めます。
けすぬ君は、時刻 $ 0 $ に高橋君たちのうちの何人かを選んで青木君にすることができます。 高橋君が青木君になっても歩く速度は変化しません。 それ以降、もしある瞬間に高橋君と青木君が同じ座標にいたなら、高橋君は青木君になります。
けすぬ君が時刻 $ 0 $ に高橋君を青木君にする $ 2^N $ 通りの方法のうち、 十分な時間が経過した後、高橋君が全員青木君になっているような方法の数を $ 10^9+7 $ で割ったあまりを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ X_1 $ $ V_1 $ : $ X_N $ $ V_N $
输出格式
十分な時間が経過した後、高橋君が全員青木君になっているような方法の数を $ 10^9+7 $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
3
2 5
6 1
3 7
输出样例 #1
6
输入样例 #2
4
3 7
2 9
8 16
10 8
输出样例 #2
9
说明
### 制約
- $ 1\ ≦\ N\ ≦\ 200000 $
- $ 1\ ≦\ X_i,V_i\ ≦\ 10^9(1\ ≦\ i\ ≦\ N) $
- $ X_i,V_i $ は整数である
- $ X_i $ たちはすべて異なる
- $ V_i $ たちはすべて異なる
### Sample Explanation 1
けすぬ君が $ (2),(3),(1,2),(1,3),(2,3),(1,2,3) $ 番目の高橋君を青木君にしたとき、十分な時間が経過した後にすべての高橋君が青木君になっています。