Dynamic Programming Optimization with Convex Hull Trick
You run a chemical laboratory which contains N beakers containing certain amount of solutions. The ith beaker contains ai ml of a reactant solution. There also M chemists waiting outside your laboratory. Each chemist has a parchment of paper which has 3 integers written on it. The ith chemist’s parchment contains 3 integers of the form: li ri xi
It denotes that the ith chemist needs atleast xi ml of reactant solution but you can only take it from the bottles numbered li to ri. If you are able to meet the ith chemists needs, he is happy .
To put it more succinctly, to make the ith chemist happy, it should be possible to take some beakers from li to ri such that the sum of their solutions is at least xi.
Print the number of chemists that returned happy after their transaction with you .
Please note that a transaction with one chemist is independent of that with another chemist , that is the the values of the beakers doesn’t change for a new transaction. For each transaction consider that the values to be those that were there initially.
Input:
The first line contains 2 integers N and M.
The next line contains N integers, the ith integer denoting ai.
The next M lines are of the form: li ri xi
Output:
Output a single integer: the number of happy chemists.
Constraints:
1<=N<= 104
1<=M<=1000
1<=ai<=104
1<=li<=ri<=N
1<=xi<=109
