Queries in an Array Codechef Solution | CODE: NIUM CHALLENGE

Queries in an Array Codechef Solution

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.

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.

Output Format

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

Constraints

  • 1≤n,Q≤1051≤n,Q≤105
  • 1≤ai≤1091≤ai≤109
  • 1≤l≤r≤n1≤l≤r≤n
  • 1≤x≤109

Subtasks

  • For 10%10% of the score: 1≤n,Q≤1001≤n,Q≤100
  • For 20%20% of the score: 1≤x≤1001≤x≤100
  • Remaining 70%70%: No extra constraints.

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

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.

Register in Contest or Click here

Divide Students Into Classes Codechef Solution>>

Alphabet Difference Codechef Solution>>

Queries in an Array Codechef Solution>>

Leave a Reply

error: Content is protected !!