Sereja and Permutations
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sereja has an array A of N integers: A, A, …, A[N]. Sereja also has an integer D.
Sereja calls a permutation P, P, …, P[N] as good if the following conditions hold.
A[P] + D > A[P],
A[P] + D > A[P],
A[P[N-1]] + D > A[P[N]].
Sereja wants to sequentially perform M single-element replacement operations on the array. Each of these operations consists of choosing an index p of the array, and replacing A[p] with a new value v. Your task is to keep track of the number of good permutations P, P, …, P[N] after each operation.
InputThe first line of input contains the integers N and D described above. The next line contains N integers A, A, …, A[N]. The line after this contains a single integer, M. Each of the next M lines contain two numbers p and v, implying that the new value of A[p] is v.
OutputOutput M lines. The ith line should contain the number of good permutations modulo 109 + 7 after we perform the ith replacement operation.
- 1 ≤ N, M ≤ 105
- 1 ≤ A[i], v ≤ 109
- 1 ≤ D ≤ 1000
- 1 ≤ p ≤ N
- Subtask #1 :N, M ≤ 10 (10 points)
- Subtask #2 :N, M ≤ 20 (10 points)
- Subtask #3: N, M ≤ 1000 (20 points)
- Subtask #4: original constrains (60 points)
Input: 3 3 1 2 3 2 1 2 3 5 Output: 6 2
Example case 1. After the first replacement operation, all permutations will be good. However, after the second operation, P must be 3.
|Tags||feb16, medium-hard, sereja|
|Time Limit:||2 - 8 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.