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("%d\n" , minimum(0 , n - 1 , l , r));
}
if (o == 4) {
printf("%lld\n" , 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("%lld\n", minmize(1, n, 1, l, r));
}
if( ty == 4 )
{
printf("%lld\n", get(1, n, 1, l, r));
}
if( cnt > 1e8 )
{
a[-inf] = 100;
return -1;
}
}
return 0;
}
0 Comments