Queries in an Array solution codechef

Queries in an Array solution codechef

Chef has an array aa consisting of positive integers. This array is sorted in non-decreasing order from left to right.

You are given QQ queries. Each query consists of three integers l,r,xl,r,x. The answer to this query can be found as follows. Consider the subarray al,al+1,,aral,al+1,…,ar. The answer to the query is the count of numbers in this subarray that are greater than or equal to xx.

Queries in an Array solution codechef Input Format

  • The first line of each test case contains two space-separated integers n,Qn,Q.
  • The second line contains nn space separated integers denoting the array aa.
  • Each of the next QQ lines contains three space-separated integers l,r,xl,r,x denoting the query.

Queries in an Array solution codechef Output Format

Output QQ lines one for each query containing the answer for the corresponding query.

Constraints

  • 1n,Q1051≤n,Q≤105
  • 1ai1091≤ai≤109
  • 1lrn1≤l≤r≤n
  • 1x1091≤x≤109

Subtasks

Queries in an Array solution codechef Sample Input 1 

5 6
1 2 3 6 9
1 5 1
1 5 3
1 5 10
1 4 4
2 5 4
2 5 1

Queries in an Array solution codechef Sample Output 1 

5
3
0
1
2
4

Explanation

  • For the first query, all the elements of the array are 1≥1. Thus, the answer is 55.
  • For the second query, the answer will be 33, as the elements 3,6,93,6,9 are 3≥3.

Leave a Comment

Your email address will not be published. Required fields are marked *