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
andk
. You are required to addk
to the value at all the indices froma
tob
(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;
}