PROBLEM LINK:
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
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[1] = start[1];
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[1] << endl;
else
cout << reverseDP[atLeastCoin] << endl;
}
return 0;
}