Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
In Burger Town new burger restaurants will be opened! Concretely, N restaurants will open in N days, while restaurant i will be opened on day i nd will be located at Xi- The town should be imagined as an one dimensional line in which every object's location can be described by the x coordinate.
Tim has just recently arrived the town after a very bad result in a programming contest. Thus he wants to cheer himself up by starting a trip to try out some new burgers.
Every burger restaurant i is associated with two integers Ai and Bi . If Tim eats a burger from i , then his happiness will increase by Ai , which can also be negative, depending on the deliciousness of the burger. On the other hand, if Tim looks through the window of an opened restaurant i , from which he will not eat a burger, then his happiness decreases by Bi , since Tim gets sad by only seeing the burgers. Tim's journey can start from any day d at the burger restaurant d and eats a burger from there. On each subsequent day n > d Tim has the following options:
- Stay at the previous restaurant p.
- Or go to the new restaurant n to eat a burger from there.
If he decides for the latter option, then on the path from p to n he will look through all the windows that are on his path and maybe lose some happiness. Concretely, if Xp < Xn, then he will look through the window of every opened restaurant i having Xp <= Xi <= Xn . Similar for the case Xn < Xp.
Since Tim is a very good friend of yours you should help him finding a trip that will maximize his happiness. If he should stay at home since no trip would cheer him up, then print 0.
Note: Tim's happiness is 0 at the beginning of the trip and is allowed to be negative throughout the time.
Input Format
N will be given on the first line, then N lines will follow, describing the restaurants numbered from 1 to N accordingly. Restaurant i will be described by Xi,Ai and Bi separated by a single space.
Output Format
Output the maximium happiness on one line.
Constraints
- 1 <= N <= 10**5
- |Ai| <= 10**6
- 0 <= Bi <= 10**6
- 0 <= Xi <= 10**9 and no two restaurants will have the same X coordinates.
Sample Input
3
2 -5 1
1 5 1
3 5 1
Sample Output
8
Sample Input
4
4 10 0
1 -5 0
3 0 10
2 10 0
Sample Output
15
Sample Input
3
1 -1 0
2 -2 0
3 -3 0
Sample Output
0
First testcase: His trip starts on day 2 at restaurant 2 located at X2 = 1 . He gains A2 = 5 happiness points there by eating a burger. On the next day he goes from restaurant 2 to 3, but will look through the window of restaurant 2 and 1. Therefore he loses B2 = 1 and B1 = 1 points on the way to restaurant 3. There he eats a burger and gains another A3 = 5 points. In total his happiness is equal to 5 - 1 - 1 + 5 = 8 and this is optimal.
Second testcase: His trip starts on day 1 at restaurant 1. Then his actions on day 2, 3 and 4 will be go to restaurant 2, stay at restaurant 2 and go to restaurant 4 respectively. The happiness of this optimal trip is equal to 10 - 5 + 10 = 15. Third testcase: It's not worth to start the trip from any of the restaurant since he will only have negative happiness. That's why he should stay at home and 0 should be printed.
Code Examples
#1 Code Example with C Programming
Code -
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;
}
#2 Code Example with C++ Programming
Code -
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;
}
#3 Code Example with Java Programming
Code -
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());
}
}