Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerRank Burger Happiness problem solution

YASH PAL, 31 July 2024

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.

HackerRank Burger Happiness problem solution

Problem solution in Java Programming.

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

public class BurgerHappiness {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    static class Node {
        static final long INF = Long.MAX_VALUE / 4;
        int l, r;
        Node left, right;
        long add;
        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() {
            return max + add;
        }

        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;
            }
            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) {
                add += delta;
                return;
            }
            left.qAdd(ql, qr, delta);
            right.qAdd(ql, qr, delta);
            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);
            pref.qAdd(pos, n, -b[i]);
            suff.qAdd(0, pos + 1, -b[i]);
            pref.qAdd(pos, pos + 1, val);
            suff.qAdd(pos, pos + 1, val);
        }
        out.println(ans);
    }

    BurgerHappiness() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        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 {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } 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("%lldn", 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;
}

coding problems data structure

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
©2025 Programming101 | WordPress Theme by SuperbThemes
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions