Redaksiya

Let's create an array $cnt$ as a counter. For each query $[l,r]$, we'll perform two operations: $cnt[l]++$ and $cnt[r+1]--$. Thus, the partial sum $\sum _{j=1}^{i}cnt[j]$ will equal the number of coins in the $i$-th coin box.

The number of days Roy performs actions is no more than $10^6$. Each day he puts no more than one coin in each coin box. After completing all the actions, each coin box will contain no more than $10^6$ coins. Create an array $coins$ of size $10^6$ and assign to $coins[i]$ the number of coin boxes with $i$ coins. To do this, for each partial sum $sum=\sum _{j=1}^{i}cnt[j]$ execute $coins[sum]++$.

Now let's find the number of coin boxes that contain at least $x$ coins. To do this, compute the partial sums in the $coins$ array from right to left (that is, from the end). Then the number of coin boxes that contain at least $x$ coins equals $coins[x]$.

Example

We get the following distribution of coins by coin boxes:

The number of coin boxes with a sum of $s$. Partial sums (counted from right to left) indicate the number of coin boxes with at least $s$ coins.

There is one coin box with a sum of $0$ (coin box number $7$), two coin boxes with a sum of $1$ (coin boxes numbered $4$ and $6$), three coin boxes with a sum of $2$ (coin boxes numbered $1,3$ and $5$), and one coin box with a sum of $3$ (coin box number $2$).

After computing the partial sums of the $coins$ array, it can be stated, for example, that there are $6$ coin boxes containing at least $1$ coin or that there are $4$ coin boxes containing at least $2$ coins.

Algorithm realization

Declare the arrays.

#define MAX 1000010
int cnt[MAX], coins[MAX];

Read the input data. Construct the array $cnt$.

scanf("%d %d",&n,&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&l,&r);
  cnt[l]++; cnt[r+1]--;
}

Compute the partial sums of the $cnt$ array in the variable $sum$. The $i$-th partial sum equals the number of coins in the $i$-th coin box. $coins[i]$ equals the number of coin boxes with a sum of $i$.

sum = 0;
for(i = 1; i <= n; i++)
{
  sum += cnt[i];
  coins[sum]++;
}

Recompute the partial sums in the $coins$ array from right to left.

for(i = MAX - 2; i >= 0; i--)
  coins[i] += coins[i+1];

Read the number of queries $q$. For each query, read the value $x$ and print the answer $coins[x]$.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d",&x);
  printf("%d\n",coins[x]);
}

Python realization

Declare the lists.

MAX = 1000010
cnt = [0] * MAX
coins = [0] * MAX

Read the input data.

n = int(input())
m = int(input())

Construct the list $cnt$.

for _ in range(m):
  l, r = map(int, input().split())
  cnt[l] += 1
  cnt[r + 1] -= 1

Compute the partial sums of the $cnt$ list in the variable $sum$. The $i$-th partial sum equals the number of coins in the $i$-th coin box. $coins[i]$ equals the number of coin boxes with a sum of $i$.

sum = 0
for i in range(1, n + 1):
  sum += cnt[i]
  coins[sum] += 1

Recompute the partial sums in the $coins$ list from right to left.

for i in range(MAX - 2, -1, -1):
  coins[i] += coins[i + 1]

Read the number of queries $q$. For each query, read the value $x$ and print the answer $coins[x]$.

q = int(input())
for _ in range(q):
  x = int(input())
  print(coins[x])