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