HackerRank Box Operations problem solution YASH PAL, 31 July 2024 In this HackerRank Box Operations problem solution, we are given n the value of each box and q operations. we need to perform all the operations efficiently. Problem solution in Java Programming. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Solution { static int func(int p, int q) { if (p >= 0) { return p / q; } return -((-p + q - 1) / q); } static final int inf = (int) (2e9) + (int) (1e8); static class Tree { long[] sum; int[] vmin; int[] vmax; int[] add; int base; Tree(int n) { base = (1 << (32 - Integer.numberOfLeadingZeros(n))); sum = new long[base * 2]; vmin = new int[base * 2]; vmax = new int[base * 2]; add = new int[base * 2]; } private void update(int u) { vmin[u] = Math.min(vmin[u * 2], vmin[u * 2 + 1]); vmax[u] = Math.max(vmax[u * 2], vmax[u * 2 + 1]); sum[u] = sum[u * 2] + sum[u * 2 + 1]; } private void putVal(int u, int val, int len) { add[u] += val; vmin[u] += val; vmax[u] += val; sum[u] += val * len; } private void push(int u, int cl, int cr) { if (add[u] != 0) { int len = (cr - cl) / 2; putVal(u * 2, add[u], len); putVal(u * 2 + 1, add[u], len); add[u] = 0; } } long getSum(int l, int r) { return getSum(l, r, 1, 0, base); } private long getSum(int l, int r, int v, int cl, int cr) { if (l <= cl && cr <= r) { return sum[v]; } if (r <= cl || cr <= l) { return 0; } int cc = (cl + cr) / 2; push(v, cl, cr); return getSum(l, r, v * 2, cl, cc) + getSum(l, r, v * 2 + 1, cc, cr); } int getMin(int l, int r) { return getMin(l, r, 1, 0, base); } private int getMin(int l, int r, int v, int cl, int cr) { if (l <= cl && cr <= r) { return vmin[v]; } if (r <= cl || cr <= l) { return inf; } int cc = (cl + cr) / 2; push(v, cl, cr); return Math.min(getMin(l, r, v * 2, cl, cc), getMin(l, r, v * 2 + 1, cc, cr)); } void put(int l, int r, int delta) { put(l, r, delta, 1, 0, base); } private void put(int l, int r, int delta, int v, int cl, int cr) { if (l <= cl && cr <= r) { putVal(v, delta, cr - cl); return; } if (r <= cl || cr <= l) { return; } int cc = (cl + cr) / 2; push(v, cl, cr); put(l, r, delta, v * 2, cl, cc); put(l, r, delta, v * 2 + 1, cc, cr); update(v); } private void divide(int l, int r, int x) { divide(l, r, x, 1, 0, base); } private void divide(int l, int r, int x, int v, int cl, int cr) { if (x == 1) { return; } if (l <= cl && cr <= r) { int d1 = func(vmin[v], x) - vmin[v]; int d2 = func(vmax[v], x) - vmax[v]; if (d1 == d2) { putVal(v, d1, cr - cl); return; } } if (r <= cl || cr <= l) { return; } int cc = (cl + cr) / 2; push(v, cl, cr); divide(l, r, x, v * 2, cl, cc); divide(l, r, x, v * 2 + 1, cc, cr); update(v); } void build(int n) { for (int i = n + base; i < 2 * base; i++) { vmin[i] = inf; vmax[i] = -inf; } for (int i = base - 1; i > 0; i--) { update(i); } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); Tree t = new Tree(n); int[] box = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { int item = Integer.parseInt(st.nextToken()); box[i] = item; t.sum[i + t.base] = t.vmin[i + t.base] = t.vmax[i + t.base] = item; } t.build(n); for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int op = Integer.parseInt(st.nextToken()); int l = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()) + 1; if (op == 1) { int x = Integer.parseInt(st.nextToken()); t.put(l, r, x); } else if (op == 2) { int x = Integer.parseInt(st.nextToken()); t.divide(l, r, x); } else if (op == 3) { bw.write(t.getMin(l, r) + "n"); } else if (op == 4) { bw.write(t.getSum(l, r) + "n"); } } bw.close(); br.close(); } } Problem solution in C++ programming. #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; typedef long long LL; inline int Div(int x , int d) { return x >= 0 ? x / d : -((-x + d - 1) / d); } int n , m , a[N]; inline int id(int l , int r) { return l + r | l != r; } #define MID int mid = l + r >> 1 #define Left l , mid #define Right mid + 1 , r struct stree { int mx , mn , f; LL s; void add(int w , int len) { mx += w; mn += w; f += w; s += (LL)len * w; } } t[N << 1]; void pushdown(int p , int l , int mid , int r) { if (t[p].f) { t[id(Left)].add(t[p].f , mid - l + 1); t[id(Right)].add(t[p].f , r - mid); t[p].f = 0; } } void pushup(int p , int l , int mid , int r) { int L = id(Left) , R = id(Right); t[p].mx = max(t[L].mx , t[R].mx); t[p].mn = min(t[L].mn , t[R].mn); t[p].s = t[L].s + t[R].s; } void build(int l , int r) { int p = id(l , r); t[p].f = 0; if (l == r) { t[p].mx = t[p].mn = t[p].s = a[l]; } else { MID; build(Left); build(Right); pushup(p , l , mid , r); } } void add(int l , int r , int top , int bot , int w) { int p = id(l , r); if (top <= l && r <= bot) { t[p].add(w , r - l + 1); } else { MID; pushdown(p , l , mid , r); if (top <= mid) add(Left , top , bot , w); if (bot > mid) add(Right , top , bot , w); pushup(p , l , mid , r); } } LL sum(int l , int r , int top , int bot) { int p = id(l , r); if (top <= l && r <= bot) { return t[p].s; } else { MID; pushdown(p , l , mid , r); LL res = 0; if (top <= mid) res += sum(Left , top , bot); if (bot > mid) res += sum(Right , top , bot); return res; } } int minimum(int l , int r , int top , int bot) { int p = id(l , r); if (top <= l && r <= bot) { return t[p].mn; } else { MID; pushdown(p , l , mid , r); int res = 0x7FFFFFFF; if (top <= mid) res = min(res , minimum(Left , top , bot)); if (bot > mid) res = min(res , minimum(Right , top , bot)); return res; } } void divide(int l , int r , int top , int bot , int d) { int p = id(l , r); bool stop = 0; if (top <= l && r <= bot) { if (t[p].mx == t[p].mn) stop = 1; int delta = t[p].mx - t[p].mn; int t1 = Div(t[p].mx , d); int t0 = Div(t[p].mn , d); if (t1 - t0 == delta) stop = 1; } if (stop || l == r) { t[p].add(Div(t[p].mx , d) - t[p].mx , r - l + 1); } else { MID; pushdown(p , l , mid , r); if (top <= mid) divide(Left , top , bot , d); if (bot > mid) divide(Right , top , bot , d); pushup(p , l , mid , r); } } int main() { scanf("%d%d" , &n , &m); for (int i = 0 ; i < n ; ++ i) { scanf("%d" , a + i); } build(0 , n - 1); for (int i = 0 ; i < m ; ++ i) { int o , l , r , w; scanf("%d%d%d" , &o , &l , &r); if (o == 1) { scanf("%d" , &w); add(0 , n - 1 , l , r , w); } if (o == 2) { scanf("%d" , &w); divide(0 , n - 1 , l , r , w); } if (o == 3) { printf("%dn" , minimum(0 , n - 1 , l , r)); } if (o == 4) { printf("%lldn" , sum(0 , n - 1 , l , r)); } } } Problem solution in C programming. #include<stdio.h> #define N 110000 #define M 550000 long long tmp[M], mi[M], mx[M], sum[M]; void tpl(int v, long long c, int len) { tmp[v] += c; sum[v] += c * len; mx[v] += c; mi[v] += c; } void update(int v, int l, int r) { if(tmp[v]) { int mid = ( l + r ) / 2; tpl(v+v, tmp[v], mid-l+1); tpl(v+v+1, tmp[v], r-mid); tmp[v] = 0; } } int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } void add(int l, int r, int v, int x, int y, long long c) { if( l == x && r == y ) { tmp[v] += c; sum[v] += c * ( r - l + 1 ); mx[v] += c; mi[v] += c; return; } else { update(v, l, r); } int mid = ( l + r ) / 2; if( y <= mid ) { add(l, mid, v+v, x, y, c); } else if( x > mid ) { add(mid+1, r, v+v+1, x, y, c); } else { add(l, mid, v+v, x, mid, c), add(mid+1, r, v+v+1, mid+1, y, c); } sum[v] = sum[v+v] + sum[v+v+1]; mi[v] = min(mi[v+v], mi[v+v+1]); mx[v] = max(mx[v+v], mx[v+v+1]); } const long long inf = 5e9; int cnt; void div(int l, int r, int v, int x, int y, long long c) { cnt++; if( l == x && r == y && mi[v] >= mx[v]-1 && ( ( mi[v] + c * inf ) / c - inf - mi[v] ) == ( ( mx[v] + c * inf ) / c - inf - mx[v] ) ) { if( mi[v] > 0 ) { c = mi[v] / c - mi[v]; } else { c = ( mi[v] + c * inf ) / c - inf - mi[v]; } tmp[v] += c; sum[v] += c * ( r - l + 1 ); mx[v] += c; mi[v] += c; return; } update(v, l, r); int mid = ( l + r ) / 2; if( y <= mid ) { div(l, mid, v+v, x, y, c); } else if( x > mid ) { div(mid+1, r, v+v+1, x, y, c); } else { div(l, mid, v+v, x, mid, c), div(mid+1, r, v+v+1, mid+1, y, c); } sum[v] = sum[v+v] + sum[v+v+1]; mi[v] = min(mi[v+v], mi[v+v+1]); mx[v] = max(mx[v+v], mx[v+v+1]); } long long minmize(int l, int r, int v, int x, int y) { if( l == x && r == y ) { return mi[v]; } else { update(v, l, r); } int mid = ( l + r ) / 2; if( y <= mid ) { return minmize(l, mid, v+v, x, y); } else if( x > mid ) { return minmize(mid+1, r, v+v+1, x, y); } else { return min(minmize(l, mid, v+v, x, mid), minmize(mid+1, r, v+v+1, mid+1, y)); } } long long get(int l, int r, int v, int x, int y) { if( l == x && r == y ) { return sum[v]; } else { update(v, l, r); } int mid = ( l + r ) / 2; if( y <= mid ) { return get(l, mid, v+v, x, y); } else if( x > mid ) { return get(mid+1, r, v+v+1, x, y); } else { return get(l, mid, v+v, x, mid) + get(mid+1, r, v+v+1, mid+1, y); } } int a[N]; int main() { int n, q, i; scanf("%d%d", &n, &q); for( i = 1 ; i <= n ; i++ ) { scanf("%d", &a[i]), add(1, n, 1, i, i, a[i]); } for( i = 1 ; i <= q ; i++ ) { int ty, l, r; scanf("%d%d%d", &ty, &l, &r); l++; r++; if( ty == 1 ) { int c; scanf("%d", &c); add(1, n, 1, l, r, c); } if( ty == 2 ) { int c; scanf("%d", &c); div(1, n, 1, l, r, c); } else if( ty == 3 ) { printf("%lldn", minmize(1, n, 1, l, r)); } if( ty == 4 ) { printf("%lldn", get(1, n, 1, l, r)); } if( cnt > 1e8 ) { a[-inf] = 100; return -1; } } return 0; } coding problems data structure