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 {

    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("%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;
}