 # CM1907-Editorial

Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name

EASY-MEDIUM.

DP, Math

# PROBLEM:

Sumit has N numbered marble boxes numbered from 1 to N. Every day he selects two indices [L,R] and adds 1 marble to each marble box starting from L to R (both inclusive). He does this for M number of days. After M days, Sumit has a query: How many marble boxes have atleast X number marble. He has Q such queries.

# EXPLANATION:

The trivial solution that comes to mind is to create an array of size N and for each update [L,R] , update 1 to each array index within this range. Then at the end, for each X , count by traversing the whole array, the number of boxes with this many or more number of coins.
One can easily figure out from the constraints that this solution is too slow to pass.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

int main(){
int n;
cin >> n;

int m;
cin >> m;

int * start = new int[n+1]();
int * end = new int[n+1]();

for (int i = 0; i < m; ++i)
{
int l, r;
cin >> l >> r;
start[l] += 1;
end[r] += 1;
}

int * dp = new int[n+1]();
dp = start;

for (int i = 2; i < n+1; ++i)
dp[i] = start[i] - end[i-1] + dp[i-1];

int * reverseDP = new int[n+1]();

for (int i = 1; i < n+1; ++i)
{
int coin = dp[i];
reverseDP[coin] += 1;
}

for (int i = m-1; i >= 1; --i)
{
reverseDP[i] += reverseDP[i+1];
}

int q;
cin >> q;

while(q--){
int atLeastCoin;
cin >> atLeastCoin;

if(atLeastCoin == 0)
cout << n - reverseDP << endl;
else
cout << reverseDP[atLeastCoin] << endl;
}

return 0;
}
``````

This is not an editorial as far as I know. An editorial explains the approach, whereas you have only told what does not work, and have given the code. Can you elaborate a little more?