第 14 回 日本情報オリンピック　模擬予選 ６

2014年12月13日
kagamiz

問題

二次元平面上の 4 点 (P_i, P_j, P_k, P_l) について, 次のすべての条件を満たすとき, これらは Y 字 であるという. なお, 以下の説明では X_n で P_n の x 座標, Y_n で P_n の Y 座標を表す.

1. X_i < X_j かつ Y_i < Y_j.
   
2. X_j < X_k かつ Y_j < Y_k < Y_j + (X_k - X_j).
   
3. X_j < X_l < X_j + (Y_l - Y_j) かつ Y_j < Y_l.

二次元平面上に N 個の点が与えられたとき, 平面上の Y 字の個数を 1000000007 で割ったあまりを求めよ.

入力

入力は M + 1 行からなる.
1 行目には 2 つの整数 N, M, A, B ( 1 ≦ N ≦ 100000, 0 ≦ M ≦ min(N, 1000), 1 ≦ A, B ≦ 10⁹ ) が空白を区切りとして書かれている.
1 + i (1 ≦ i ≦ M) 行目には, 整数 Xi と Yi (-10⁹ ≦ Xi, Yi ≦ 10⁹) が空白を区切りとして書かれている. これは i 番目の点の X 座標および Y 座標の値を表している.
残りの N - M 個の点は, 以下の C++ 言語のコードを用いて作られる.

unsigned int r(){ 
	static unsigned int  x = 123456789,
	                     y = 362436069,
	                     z = 521288629,
	                     w = A;
	unsigned int t = (x ^ (x << 11)); 
	x = y; y = z; z = w;
	
	return (w = (w ^ (w >> 19) ^ (t ^ (t >> 8)))); 
}

void generate(int X[], int Y[])
{
    for (int i = M + 1; i <= N; i++){
        X[i] = r() % (2 * B + 1); X[i] -= B;
        Y[i] = r() % (2 * B + 1); Y[i] -= B;
    }
}

ここで, unsigned int 型は 32 ビット符号なし整数を表現できる型とし, int 型は 32 ビットの符号付き整数を表現できる型である.

出力

1 行に, 平面上の Y 字の個数を 1000000007 で割ったあまりを求めよ.

入出力例

12 2 893 15
-14 -9
0 1



  

52 0 41592627 1000000000





  

3141 5 926 535
89 -79
-323 84
626 433
-83 -279
-5028 -8419
  

8
   

4568
   

574575671
   

入出力例 1 の 12 個の点の座標は以下のようになる :
(-14, -9), (0, 1), (-1, -15), (1, 2), (4, -6), (10, 5), (6, 6), (-11, -6), (-14, -7), (4, -11), (-3, 15), (7, -13).

この入力例では, 次の 8 つの点の組
(P₁, P₈, P₂, P₁₁), (P₁, P₈, P₄, P₁₁), (P₁, P₈, P₆, P₁₁), (P₁, P₈, P₇, P₁₁), (P₉, P₈, P₂, P₁₁), (P₉, P₈, P₄, P₁₁), (P₉, P₈, P₆, P₁₁), (P₉, P₈, P₇, P₁₁)
が Y 字を構成している.

入出力例 2 の最初の 10 個の点の座標は以下のようになる :
(683709195, -523773722), (-548167861, 169658628), (-564639697, -722129819), (-352632156, 679634347), (858639724, -673351832),
(252229649, 343817880), (556729437, -75294251), (643666477, 538005726), (-803284659, -412822891), (-831170606, 577935986).

この問題は tokoharu_sakura さんから頂いた問題です. この場を借りてお礼申し上げます.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

採点用データ