CPAIR2 - Counting diff-pairs
You are given sequence A of N integers. You are also given integer K and M queries. Each query consists of two integers l, r. For each query output number of pairs i, j such that l <= i < j <= r and abs(A[i] - A[j]) >= K.
Indexing starts with 1.
N <= 50000
M <= 50000
1 <= A[i] <= 100000
NOTE: All tests are randomly generated.
First line of input contains integers N, M, K in this order.
Second line contains N integers representing array A.
Next M lines describe queries.
Output answer for each query.
Input: 3 1 2
1 2 3
n*sqrt(n)*log(n) works fine!, and it's not necessary to use printf/scanf methods
Time limit is strict .Use BIT instead of segment tree.
awesome problem, I love it
Limits of K should be mentioned. Until then it is safe to assume K can be any positive integer.
Very nice problem.