Question Name:ALGORITHMIC CRUSH

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
       long int j,i,N,M,a,b,k,max=0;
       cin>>N>>M;
       long int *ar = new long int[N]();
       for(i=0;i<M;i++)
       {
              cin>>a>>b>>k;
              ar[a-1] = ar[a-1] + k;
              if(b<N)
              {
                     ar[b] = ar[b] - k;
              }
       }
       k = 0;
       for(i=0;i<N;i++)
       {
              k = k + ar[i];
              if(k>max)
              {
                     max = k;
              }
       }
       cout<<max<<endl;
       return 0;
}
  • Problem Description
    You are given a list of size N, initialized with zeroes. You have to perform M operations on the list and output the maximum of final values of all the N elements in the list. For every operation, you are given three integers a,b and k and you have to add value k to all the elements ranging from index a to b (both inclusive).

    Input Format

    First line will contain two integers N and M separated by a single space. Next M lines will contain three integers a,b and k separated by a single space.

    Numbers in list are numbered from I to N.

    Constraints
    3<=N<=10^7 
    1<=M<=2 * 10 ^5 
    1<=a<=b<=N 
    0<=k<=10^9

    Output Format

    A single line containing maximum value in the updated list.
  • Test Case 1
    Input (stdin)5 3
    1 2 100
    2 5 100
    3 4 100
    Expected Output200
  • Test Case 2
    Input (stdin)4 2
    1 2 100
    3 4 100
    Expected Output100

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro