-3

Question:
Starting with a 1-indexed array of size n filled with all zeroes, you are required to perform the following operation m times:

Each operation contains 3 integers a, b and k. You are required to add k to the value at all the indices from a to b (both inclusive).

Once all operations have been performed, return the maximum value in the array.

Input Format:
The first line contains two space-separated integers n and m, the size of the array and the number of operations respectively.
Each of the next m lines contains three space-separated integers a, b and k, the left index, right index and integer to add respectively.

Constraints:

1 <= n, m <= 10^5
1 <= a <= b <= n
-10^9 <= k <= 10^9

Examples:

Sample Input 1:
10 3
1 5 3
4 8 7
6 9 1

Sample Output 1:
10

Explanation:
Given n = 10 and m = 3

Queries are interpreted as follows:
a b k
1 5 3
4 8 7
6 9 1

Add the values of k between the indices a and b inclusive:

     1 2 3 4 5 6 7 8 9 10 (index)

    [0,0,0,0,0,0,0,0,0,0] (Initially)

    [3,3,3,3,3,0,0,0,0,0] (After Query 1)

    [3,3,3,10,10,7,7,7,0,0] (After Query 2)

    [3,3,3,10,10,8,8,8,1,0] (After Query 3)

The largest value is 10 after all operations are performed.

Sample Input 2:

5 3
1 2 100
2 5 100
3 4 100

Sample Output:
200

Explanation:
After the first update the list is 100 100 0 0 0.
After the second update list is 100 200 100 100 100.
After the third update list is 100 200 200 200 100.

The maximum value is 200.

This code ran and gave the correct output:

#include <iostream>
#include <vector>
using namespace std;

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

  vector<long long int> arr(n, 0);

  for (int i = 0; i < m; i++) {
    int start, finish, value;
    cin >> start >> finish >> value;
    arr[start - 1] += value;
    arr[finish] -= value;
  }

  long long int ans = 0;
  long long int current = 0;

  for (int value : arr) {
    current += value;
    if (current > ans) {
      ans = current;
    }
  }

  cout << ans;

  return 0;
}

but this code is giving me segment fault:

#include <bits/stdc++.h>

using namespace std;

int main(){
    long long int n,m;
    cin>>n>>m;
    long long int x[n] ={0};
    for(int i=0;i<m;i++)
    {
        long long int a,b,k;
        cin>>a>>b>>k;
        x[a-1] += k;
        if(b<n)
           x[b] -= k;
    }
    long long int max=0,current=0;
    for(int i=0;i<n;i++)
    {
        current=x[i]+current;
        if(max<current)
            max=current;
    }
    cout<<max<< endl;
    return 0;
}
  • Please do not use both C and C++ tags. These are two different languages. Pick the one you really need. Edit your question to remove the bad one. – fpiette May 24 '21 at 08:58
  • @RAHUL MITTAL There is much common in the programs. At least the both programs are very and very bad.:) – Vlad from Moscow May 24 '21 at 09:00
  • The 2nd example isn't valid c++ code. – πάντα ῥεῖ May 24 '21 at 09:01
  • 1
    `long long int x[n] ={0};` is non-standard and you will need to check your compiler documentation to see if it does zero the whole array, just the 1st element, or something else entirely. See https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard – Richard Critten May 24 '21 at 09:09
  • @πάνταῥεῖ except for the header tag can you please state what's invalid it could be the problem with my code – RAHUL MITTAL May 24 '21 at 09:11
  • @RichardCritten ya it assigns 0 to all the elements of the array I tried it by printing the array after declaring it and I will make sure not to use this next time as its a non standerd – RAHUL MITTAL May 24 '21 at 09:18
  • @RAHUL MITTAL Why are you using the expression for index start - 1 (arr[start - 1]) but the expression finish instead of finish - 1 (arr[finish] )? This does not make a sense. – Vlad from Moscow May 24 '21 at 09:35
  • @RAHUL MITTAL Moreover the code does not correspond to the description. – Vlad from Moscow May 24 '21 at 09:39
  • @VladfromMoscow the for loop run from arr[start-1] till arr[finish] instead of arr[finish -1] as I want till arr[finish-1] the value is added but not in arr[finish] so I have assigned a negative value at arr[finish] you can try running the sample input you might understand – RAHUL MITTAL May 24 '21 at 09:44
  • @RAHULMITTAL This does not make any sense. – Vlad from Moscow May 24 '21 at 09:45
  • @RAHULMITTAL https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard – πάντα ῥεῖ May 24 '21 at 10:06

1 Answers1

0

Well the problem in your code is in the line x[b] -= k;

Since b is 1-indexed, this means that b can be upto n but your array of size n has indices from 0 to n-1 and if there is a query where b = n, then you get segmentation fault.

You can correct this by placing an if condition just before this line like this:
if (b < n)

Also, in the first code, you should have encountered the same problem but somehow your compiler overlooked the indexing problem in vector.

risingStark
  • 1,153
  • 10
  • 17
  • Thanks, bro you found an issue but it's still showing me segment fault. – RAHUL MITTAL May 24 '21 at 09:39
  • @RAHULMITTAL On my machine, its working perfectly fine now. Try running it on some online compiler like ideone.com – risingStark May 24 '21 at 09:42
  • https://www.hackerrank.com/challenges/crush/copy-from/214906404 Please try in this sample cases it works for small input but for large it doesn't – RAHUL MITTAL May 24 '21 at 09:48
  • @RAHULMITTAL This solution got accepted. Here is the [code](https://ideone.com/4KNTnZ). In this code I have used some `#define` templates to write faster code. Plz let me know if you don't understand it. – risingStark May 24 '21 at 09:58
  • @RAHULMITTAL You can consider upvoting and accepting my answer if it helped you :) – risingStark May 24 '21 at 10:00
  • @risingStark If you can not reproduce then your answer does not make a sense. – Vlad from Moscow May 24 '21 at 10:20
  • @VladfromMoscow I reproduced the error, then corrected it. He gave me the problem link to submit the answer, I submitted in that as well and got accepted. – risingStark May 24 '21 at 10:25
  • thanks, @risingStark but my question is what's the mistake in the above code – RAHUL MITTAL May 24 '21 at 13:05
  • @RAHULMITTAL That's what I told you. There is no mistake other than the one I pointed out in the answer. I got my solution accepted so it means that it is working on hackerrank judge perfectly fine – risingStark May 24 '21 at 15:13