# HackerRank Burger Happiness problem solution

In this HackerRank Burger Happiness problem solution, we have given restaurants numbered from 1 to N accordingly. we need to find the maximum happiness on one line.

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;

public class BurgerHappiness {

PrintWriter out;
StringTokenizer st;
boolean eof;

static class Node {
static final long INF = Long.MAX_VALUE / 4;
int l, r;
Node left, right;
long max;

public Node(int l, int r) {
this.l = l;
this.r = r;
if (r - l > 1) {
int mid = (l + r) >> 1;
left = new Node(l, mid);
right = new Node(mid, r);
}
}

long getMax() {
}

long qMax(int ql, int qr) {
if (l >= qr || ql >= r) {
return -INF;
}
if (ql <= l && r <= qr) {
return getMax();
}
return Math.max(left.qMax(ql, qr), right.qMax(ql, qr)) + add;
}

long get(int pos) {
if (l == pos && pos + 1 == r) {
}
return add + (pos < left.r ? left : right).get(pos);
}

void qAdd(int ql, int qr, long delta) {
if (l >= qr || ql >= r) {
return;
}
if (ql <= l && r <= qr) {
return;
}
max = Math.max(left.getMax(), right.getMax());
}
}

void solve() throws IOException {
int n = nextInt();
int[] x = new int[n];
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
x[i] = nextInt();
a[i] = nextInt();
b[i] = nextInt();
}
int[] xx = x.clone();
Arrays.sort(xx);
for (int i = 0; i < n; i++) {
x[i] = Arrays.binarySearch(xx, x[i]);
}

long ans = 0;

Node pref = new Node(0, n);
Node suff = new Node(0, n);

for (int i = 0; i < n; i++) {
int pos = x[i];
long valL = suff.qMax(0, pos + 1) - suff.get(pos);
long valR = pref.qMax(pos, n) - pref.get(pos);
long val = Math.max(valL, valR) + a[i];
ans = Math.max(ans, val);
}
out.println(ans);
}

BurgerHappiness() throws IOException {
out = new PrintWriter(System.out);
solve();
out.close();
}

public static void main(String[] args) throws IOException {
new BurgerHappiness();
}

String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}

String nextString() {
try {
} catch (IOException e) {
eof = true;
return null;
}
}

int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}

long nextLong() throws IOException {
return Long.parseLong(nextToken());
}

double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}```

## Problem solution in C++ programming.

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
const ll INF = 1LL << 62;
const int MAX_A = 1e6;
const int MAX_X = 1e9;
const int MAX_B = 1e6;

int N;
int X[MAX_N], A[MAX_N], B[MAX_N];
ll F[MAX_N];

int tmp[MAX_N];
struct SegmentTree {
ll lazy[MAX_N * 4];
ll T[MAX_N * 4];
void init(){
memset(lazy, 0, sizeof lazy);
memset(T, 0, sizeof T);
}
void propagate(int n, int L, int R){
T[n] += lazy[n];
if(L != R){
lazy[n * 2] += lazy[n];
lazy[n * 2 + 1] += lazy[n];
}
lazy[n] = 0;
}

void update(int n, int L, int R, int i, int j, ll x){
propagate(n, L, R);
if(R < i || j < L) return;
if(i <= L && R <= j){
lazy[n] = x;
propagate(n, L, R);
} else {
update(n * 2, L, (L + R) / 2, i, j, x);
update(n * 2 + 1, (L + R) / 2 + 1, R, i, j, x);
T[n] = max(T[n * 2], T[n * 2 + 1]);
}
}

void update(int i, int j, ll x){
if(i <= j)
update(1, 0, N - 1, i, j, x);
}

ll query(int n, int L, int R, int i, int j){
if(R < i || j < L) return -INF;
propagate(n, L, R);
if(i <= L && R <= j) return T[n];
return max(query(n * 2, L, (L + R) / 2, i, j),
query(n * 2 + 1, (L + R) / 2 + 1, R, i, j));
}
ll query(int i, int j){
if(i > j) return -INF;
return query(1, 0, N - 1, i, j);
}
};

SegmentTree T1; // Stores maximum f(x') + S[x' - 1]
SegmentTree T2; // Stores maximum f(x') - S[x']

ll query(int x, int a){
ll S = -T2.query(x, x);  // S[x], since F[x] = 0
ll S1 = T1.query(x, x);  // S[x - 1], since F[x] = 0
// Case x' < x
ll res1 = -S + a + T1.query(0, x - 1);
// Case x < x'
ll res2 = S1 + a + T2.query(x + 1, N - 1);
// Case Beginning from x
ll res3 = a;
return max(max(res1, res2), res3);
}

void update(int x, int b){
T1.update(x, x, F[x]);
T1.update(x + 1, N - 1, +b);

T2.update(x, x, F[x]);
T2.update(x, N - 1, -b);
}

int main(){
T1.init(), T2.init();
scanf("%d", &N);
assert(1 <= N && N <= MAX_N);
for(int i = 0; i < N; i++){
scanf("%d%d%d", X + i, A + i, B + i);
assert(0 <= X[i] && X[i] <= MAX_X);
assert(0 <= B[i] <= MAX_B);
assert(-MAX_A <= A[i] && A[i] <= MAX_A);
tmp[i] = X[i];
}
sort(tmp, tmp + N);
int m = unique(tmp, tmp + N) - tmp;
for(int i = 0; i < N; i++){
X[i] = lower_bound(tmp, tmp + m, X[i]) - tmp;
}
ll res = 0;
for(int i = 0; i < N; i++){
F[X[i]] = query(X[i], A[i]);
update(X[i], B[i]);
res = max(res, F[X[i]]);
}
printf("%lld\n", res);
return 0;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <stdlib.h>
#define INF 1000000000000000000LL
typedef struct Node {
long long offt;
long long cmax;
} node;
void init( int n );
long long range_sum( int i, int j );
void update( int i, long long val );
void updated(int n, int b, int e, int i, int j, long long val,node* tree);
long long query(int n, int b, int e, int i, int j, long long offt,node* tree);
long long max(long long a,long long b);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int X[100000],A[100000],B[100000],idx[100000],N;
long long tree[300000],ans[100000];
node left[400000]={0},right[400000]={0};

int main(){
int M,i;
long long max,max1,max2,lsum,rsum;
scanf("%d",&M);
for(i=0;i<M;i++){
scanf("%d%d%d",X+i,A+i,B+i);
idx[i]=i;
}
sort_a2(X,idx,M);
for(i=0;i<M;i++)
X[idx[i]]=i;
init(M);
for(i=0;i<M;i++){
if(X[i]!=M-1)
max1=query(1,0,M-1,X[i]+1,M-1,0,left);
else
max1=-INF;
if(X[i])
max2=query(1,0,M-1,0,X[i]-1,0,right);
else
max2=-INF;
lsum=range_sum(0,X[i]);
rsum=range_sum(X[i],M-1);
max=(max1+lsum>max2+rsum)?max1+lsum:max2+rsum;
if(max<0)
max=0;
ans[i]=A[i]+max;
updated(1,0,M-1,X[i],X[i],ans[i],left);
updated(1,0,M-1,X[i],X[i],ans[i],right);
updated(1,0,M-1,X[i],M-1,-B[i],left);
updated(1,0,M-1,0,X[i],-B[i],right);
update(X[i],B[i]);
}
for(i=max=0;i<M;i++)
if(ans[i]>max)
max=ans[i];
printf("%lld",max);
return 0;
}
void init( int n ){
N = 1;
while( N < n ) N *= 2;
int i;
for( i = 1; i < N + n; i++ ) tree[i] = 0;
}
long long range_sum( int i, int j ){
long long ans = 0;
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) ans += tree[i];
if( j % 2 == 0 ) ans += tree[j];
}
return ans;
}
void update( int i, long long val ){
long long diff = val - tree[i+N];
int j;
for( j = i + N; j; j /= 2 ) tree[j] += diff;
}
void updated(int n, int b, int e, int i, int j, long long val,node* tree){
if (b>e || i>j || b>j || e<i) return;
if (b>=i && e<=j)
{
tree[n].offt += val;
tree[n].cmax += val;
return;
}
updated(n*2 , b , (b+e)/2 , i , j , val,tree);
updated(n*2+1 , (b+e)/2 + 1 , e , i , j , val,tree);
tree[n].cmax = max ( tree[n*2].cmax , tree[n*2+1].cmax ) + tree[n].offt;
}
long long query(int n, int b, int e, int i, int j, long long offt,node* tree){
if (b>e || i>j || b>j || e<i) return -INF;
if (b>=i && e<=j)
return tree[n].cmax + offt;
offt += tree[n].offt;
return max ( query(n*2 , b , (b+e)/2 , i , j, offt,tree) , query(n*2+1 , (b+e)/2 + 1 , e , i , j, offt,tree) );
}
long long max(long long a,long long b){
return (a>b)?a:b;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}```