HackerRank Sum of the Maximums problem solution

In this HackerRank Sum of the Maximums problem, we have given an array of n integers. and we need to calculate the sum of the maximum values for all subsegments of the array.

HackerRank Sum of the Maximums problem solution

Problem solution in Java Programming.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class G3X {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), Q = ni();
        int[] a = na(n);
        int[][] qs = new int[Q][];
        for(int i = 0;i < Q;i++){
            qs[i] = new int[]{ni()-1, ni()-1, i};
        }
        
        int[] L = enumPrevWall(a);
        int[] R = enumPrevWall2(rev(a));

        rev(a);
        int[][] reaches = new int[n][];
        for(int i = 0;i < n;i++){
            reaches[i] = new int[]{L[i]+1, n-1-R[n-1-i]-1, i, a[i]};

        }
        
        int[][] lqs = Arrays.copyOf(qs, Q);
        Arrays.sort(lqs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        int[] inds = new int[Q];
        int[] iinds = new int[Q];
        int[] ys = new int[Q];
        for(int i = 0;i < Q;i++)inds[i] = lqs[i][2];
        for(int i = 0;i < Q;i++)ys[i] = lqs[i][1];
        for(int i = 0;i < Q;i++)iinds[inds[i]] = i;
        
        int[] lb = new int[n+2];
        int lp = 0;
        for(int i = 0;i <= n+1;i++){
            while(lp < ys.length && ys[lp] < i)lp++;
            lb[i] = lp;
        }
        
        long[] ret = new long[Q];
        {
            int[][] es = new int[3*n+Q][];
            for(int i = 0;i < n;i++){
                es[i] = reaches[i];
                es[n+i] = new int[]{Math.max(0, reaches[i][0]+1), Math.min(reaches[i][1]-1, i-1), i, -a[i]};
                es[2*n+i] = new int[]{Math.max(i+1, reaches[i][0]+1), 
                        Math.min(n, reaches[i][1]-1), i, -a[i]};
                reaches[i][0]++;
                reaches[i][1]--;
            }
            for(int i = 0;i < Q;i++){
                es[3*n+i] = qs[i];
            }
            
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])return -(a[0] - b[0]);
                    if(a[1] != b[1])return a[1] - b[1];
                    return a.length - b.length;
                }
            });
            
            
            long[] ft2 = new long[Q+3];
            long[] ft1 = new long[Q+3];
            long[] ft0 = new long[Q+3];
            long sft2 = 0, sft1 = 0, sft0 = 0;
            for(int[] e : es){
                if(e.length == 4){
                    int ind = lb[e[1]+1];

                    sft2 += -(long)e[3]*e[2]*e[2];
                    addFenwick(ft2, ind, (long)e[3]*e[2]*e[2]);
                    sft1 += (long)e[3]*e[2];
                    addFenwick(ft1, ind, -(long)e[3]*e[2]);
                    sft0 += (long)e[3];
                    addFenwick(ft0, ind, -e[3]);
                }else{

                    ret[e[2]] -= 
                            (sft2 + sumFenwick(ft2, iinds[e[2]])) +
                            (sft1 + sumFenwick(ft1, iinds[e[2]])) * (qs[e[2]][1]+qs[e[2]][0]) +
                            (sft0 + sumFenwick(ft0, iinds[e[2]])) * (qs[e[2]][1]+1) * (-qs[e[2]][0] + 1);
                }
            }
            for(int i = 0;i < Q;i++){
                ret[i] += 
                        (sft2 + sumFenwick(ft2, iinds[i])) +
                        (sft1 + sumFenwick(ft1, iinds[i])) * (qs[i][1]+qs[i][0]) +
                        (sft0 + sumFenwick(ft0, iinds[i])) * (qs[i][1]+1) * (-qs[i][0] + 1);
            }
            for(int i = 0;i < n;i++){
                reaches[i][0]--;
                reaches[i][1]++;
            }
        }

        
        {
            int[][] es = new int[2*n+Q][];
            for(int i = 0;i < n;i++){
                es[i] = reaches[i];
                es[n+i] = new int[]{i+1, reaches[i][1], i, -a[i]};
                reaches[i][0]++;
            }
            for(int i = 0;i < Q;i++){
                es[2*n+i] = qs[i];
            }
            
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])return -(a[0] - b[0]);
                    if(a[1] != b[1])return -(a[1] - b[1]);
                    return a.length - b.length;
                }
            });
            

            long[] ft1 = new long[Q+3];
            long[] ft0 = new long[Q+3];
            for(int[] e : es){
                if(e.length == 4){
                    int ind = lb[e[1]];

                    addFenwick(ft1, ind, -(long)e[3]*(e[1]-e[2]+1));
                    addFenwick(ft0, ind, (long)e[3]*(e[1]-e[2]+1)*(e[2]+1));
                }else{
                    ret[e[2]] -= 
                            sumFenwick(ft1, iinds[e[2]]) * qs[e[2]][0] +
                            sumFenwick(ft0, iinds[e[2]]);
                }
            }
            long[] imos1 = dominatorFenwick(ft1);
            long[] imos0 = dominatorFenwick(ft0);
            for(int i = 0;i < Q;i++){
                ret[i] += imos1[iinds[i]] * qs[i][1] + imos0[iinds[i]];
            }

            for(int i = 0;i < n;i++){
                reaches[i][0]--;
            }
        }

        {
            int[][] es = new int[2*n+Q][];
            for(int i = 0;i < n;i++){
                es[i] = reaches[i];
                es[n+i] = new int[]{reaches[i][0], i-1, i, -a[i]};
                reaches[i][1]--;
            }
            for(int i = 0;i < Q;i++){
                es[2*n+i] = qs[i];
            }
            
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])return (a[0] - b[0]);
                    if(a[1] != b[1])return (a[1] - b[1]);
                    return a.length - b.length;
                }
            });
            

            long[] ft1 = new long[Q+3];
            long[] ft0 = new long[Q+3];
            long sft1 = 0, sft0 = 0;
            for(int[] e : es){
                if(e.length == 4){
                    int ind = lb[e[1]+1];

                    sft1 += (long)e[3]*(e[2]-e[0]+1);
                    addFenwick(ft1, ind, -(long)e[3]*(e[2]-e[0]+1));
                    sft0 += (long)e[3]*(e[2]-e[0]+1)*(-e[2]+1);
                    addFenwick(ft0, ind, -(long)e[3]*(e[2]-e[0]+1)*(-e[2]+1));
                }else{
                    ret[e[2]] -= 
                            (sft1 + sumFenwick(ft1, iinds[e[2]])) * qs[e[2]][1] +
                            (sft0 + sumFenwick(ft0, iinds[e[2]]));
                }
            }
            long[] imos1 = dominatorFenwick(ft1);
            long[] imos0 = dominatorFenwick(ft0);
            for(int i = 0;i < Q;i++){
                ret[i] += (sft1 + imos1[iinds[i]+1]) * qs[i][1] + sft0 + imos0[iinds[i]+1];
            }
            for(int i = 0;i < n;i++){
                reaches[i][1]++;
            }
        }
        
        {
            long[] es = new long[n+Q];
            for(int i = 0;i < n;i++){
                es[i] = (long)n+1-reaches[i][0]<<40|(long)reaches[i][1]<<20|0<<19|i;
            }
            for(int i = 0;i < Q;i++){
                es[n+i] = (long)n+1-qs[i][0]<<40|(long)qs[i][1]<<20|1<<19|i;
            }
            
            Arrays.sort(es);
            
            long[] nft = new long[Q+3];
            for(long e : es){
                long e0 = n+1-(e>>>40);
                long e1 = e>>>20&(1L<<20)-1;
                long e2 = e&(1L<<19)-1;
                if(e<<~19>=0){
                    long e3 = a[(int)e2];
                    int ind = lb[(int)e1];
                    addFenwick(nft, ind, (long)e3*(e1-e2+1)*(e2-e0+1));
                }else{
                    ret[(int)e2] += sumFenwick(nft, iinds[(int)e2]);
                }
            }
        }

        for(long v : ret){
            out.println(v);
        }
    }
    
    public static long[] dominatorFenwick(long[] ft)
    {
        int n = ft.length;
        long[] imos = new long[n];
        for(int i = 1;i <= n-1;i++){
            imos[i] += ft[i];
            imos[Math.min(n-1, i+(i&-i))] -= ft[i];
        }
        for(int i = 0;i <= n-2;i++){
            imos[i+1] += imos[i];
        }
        return imos;
    }
    
    public static int lowerBound(int[] a, int v)
    {
        int low = -1, high = a.length;
        while(high-low > 1){
            int h = high+low>>>1;
            if(a[h] >= v){
                high = h;
            }else{
                low = h;
            }
        }
        return high;
    }
    
    public static long sumFenwick(long[] ft, int i)
    {
        long sum = 0;
        for(i++;i > 0;i -= i&-i)sum += ft[i];
        return sum;
    }
    
    public static void addFenwick(long[] ft, int i, long v)
    {
        if(v == 0)return;
        int n = ft.length;
        for(i++;i < n;i += i&-i)ft[i] += v;
    }

    
    public static int[] rev(int... a){ for(int i = 0, j = a.length-1;i < j;i++,j--){ int d = a[i]; a[i] = a[j]; a[j] = d;}return a; }
    
    public static int[] enumPrevWall(int[] a)
    {
        int n = a.length;
        int[] L = new int[n];
        for(int i = 0;i < n;i++){
            L[i] = i-1;
            while(L[i] >= 0 && a[L[i]] < a[i])L[i] = L[L[i]];
        }
        return L;
    }
    
    public static int[] enumPrevWall2(int[] a)
    {
        int n = a.length;
        int[] L = new int[n];
        for(int i = 0;i < n;i++){
            L[i] = i-1;
            while(L[i] >= 0 && a[L[i]] <= a[i])L[i] = L[L[i]];
        }
        return L;
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new G3X().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Problem solution in C++ programming.

#include<bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int>   II;
typedef vector< II >      VII;
typedef vector<int>     VI;
typedef vector< VI >    VVI;
typedef long long int   LL;
 
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
 
#define si(n) scanf("%d",&n)
#define dout(n) printf("%dn",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lldn",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
 
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
 
const int N = int(1.35*1e5)+10;
const int SQRT = 400;
LL A[N],dp[N],dp2[N],PS[N],ans[N],dp3[N];
int st[N],top,arr[N],len,st2[N],top2;
VI B[N];
struct query{
  int l,r;
}Q[N];
bool cmp(int i,int j){
  return Q[i].r < Q[j].r;
}
LL get2(int ll,int rr,int n,int L,int len){
  LL ret = 0;assert(len>0);LL mx = -int(1e9);
  for(int i=rr;i>=ll;i--){
    mx = max(mx,A[i]);
    if(mx >= A[arr[len]]){ret += mx*(n + 1 - L);continue;}
    int l = 1, h = len, ans = 0;
    while(l<=h){
      int m = (l+h)/2;
      if(A[arr[m]] >= mx){ans = m;h = m-1;}
      else l = m+1;
    }
    ret += (mx*(arr[ans]-L));
    ret += PS[len]-PS[ans-1];
  }
  return ret;
}
LL get(int l,int r){
  LL ret = 0;top2=0;
  int R = l;
  while(R <= r){
    while(top2 && A[st2[top2]] <= A[R])top2--;
    int lpos = (top2?st2[top2]:l-1);
    dp3[R] = (R -lpos)*A[R] + (top2?dp3[lpos]:0);
    st2[++top2]=R;
    ret+=dp3[R];
    R++;
  }
  return ret;
}
int main()
{
  int n,q;
  si(n);si(q);
  for(int i=1;i<=n;i++)sll(A[i]);
  for(int i=1;i<=q;i++){
    si(Q[i].l);si(Q[i].r);
    B[Q[i].l/SQRT].PB(i);
  }
  for(int i=0;i<N;i++){
    sort(ALL(B[i]),cmp);
    int L = (i+1)*SQRT, R = L;top = len = 0;
    LL add = 0;
    for(int j=0;j<SZ(B[i]);j++){
      int idx = B[i][j];
      int l = Q[idx].l,r = Q[idx].r;
      ans[idx] = get(l,min(r,L-1));
      if(r<L)continue;
      while(R <= r){
        while(top && A[st[top]] <= A[R])top--;
        int lpos = (top?st[top]:L-1);
        dp2[R] = (R -lpos)*A[R] + (top?dp2[lpos]:0);
        st[++top] = R;
        if(!len || A[R]>A[arr[len]]){
          if(len){
            dp[arr[len]] = (R - arr[len])*A[arr[len]];
            PS[len] = PS[len-1] + dp[arr[len]];
          }
          arr[++len]=R;
          dp[R] = (r - R + 1)*A[R];
          PS[len] = PS[len-1] + dp[R];
        }
        add += dp2[R];R++;
      }
      dp[arr[len]] = (r - arr[len] + 1)* A[arr[len]];
      PS[len] = PS[len-1] + dp[arr[len]];
      ans[idx] += add;
      ans[idx] += get2(l,L-1,r,L,len);
    }
  }
  for(int i=1;i<=q;i++)
    lldout(ans[i]);
  return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


unsigned floor_square_root(unsigned self) {
    
    unsigned
        root = 0,
        length = self;

    while (length > 1)
        if ((root * root + length * ((length >> 2) + root)) < self) {
            root += length >> 1;
            length -= length >> 1;
        } else
            length >>= 1;

    return root;
}

unsigned floor_log2(unsigned self) {
    static const unsigned de_bruijn[] = {
        0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
        8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
    };

    self |= self >> 1;
    self |= self >> 2;
    self |= self >> 4;
    self |= self >> 8;
    self |= self >> 16;

    return de_bruijn[(self * 0x07C4ACDDU) >> 27];
}

static inline unsigned arg_max(
    unsigned length,
    unsigned log2_limit,
    unsigned (*max)[length][log2_limit],
    long *weights,
    unsigned low,
    unsigned high
) {
    unsigned length_log2 = floor_log2(high - low + 1);
    return max[0][
        ((weights[max[0][low][length_log2]] > weights[max[0][(high - (1U << length_log2) + 1)][length_log2]])
            ? low : (high - (1U << length_log2) + 1))
    ][length_log2];
}

int main(int argc, const char * argv[]) {
    unsigned at, others, count, query_cnt;
    scanf("%u %u", &count, &query_cnt);

    long items[count + 2];
    for (at = 1; at <= count; scanf("%ld", &items[at++]));

    unsigned
        history[count + 1],
        log2_limit = floor_log2(count + 1) + 1;

    unsigned (*max)[count + 1][log2_limit] = malloc(sizeof(unsigned) * (count + 1) * log2_limit);
    for (at = 0; ++at <= count; max[0][at][0] = at);

    unsigned log2_length;
    for (log2_length = 0; (log2_length + 1) < log2_limit; log2_length++)
        for (at = 0; (++at + (1 << log2_length)) <= count;
             max[0][at][log2_length + 1] = max[0][at +
                ((items[max[0][at][log2_length]] < items[max[0][at + (1U << log2_length)][log2_length]])
                    << log2_length)
            ][log2_length]);

    long
        end_sums[count + 2],
        start_sums[count + 2];

    unsigned
        left_greater[count + 1],
        right_greater[count + 1];

    items[history[0] = 0] = 0x7FFFFFFFFFFFFFFFL;
    end_sums[0] = 0;
    for (others = (at = 1); at <= count; history[others++] = at++) {
        for (; items[history[others - 1]] <= items[at]; others--);
        left_greater[at] = history[others - 1];

        end_sums[at] = items[at] * (at - left_greater[at]) + end_sums[left_greater[at]];
    }

    items[history[0] = (count + 1)] = 0x7FFFFFFFFFFFFFFFL;
    start_sums[count + 1] = 0;
    for (others = 1; --at; history[others++] = at) {
        for (; items[history[others - 1]] <= items[at]; others--);
        right_greater[at] = history[others - 1];

        start_sums[at] = items[at] * (right_greater[at] - at) + start_sums[right_greater[at]];
    }

    unsigned
        block_length = floor_square_root(count + 1);

    long
        total,
        spans[((count + 1) / block_length) + 1][((count + 1) / block_length) + 1];

    memset(spans, 0, sizeof(spans));
    for (at = 1; at <= count; at += block_length) {
        long sums[count + 1];
        total = 0;

        for (others = at; others <= count; others++) {
            sums[others]
                = (left_greater[others] < at)
                ? (items[others] * (others - at + 1))
                : (items[others] * (others - left_greater[others]) + sums[left_greater[others]]);

            total += sums[others];
            if ((others % block_length) == 0)
                spans[at / block_length][others / block_length] = total;
        }
    }

    unsigned low, high;
    for (; query_cnt--; printf("%ldn", total + spans[low / block_length][high / block_length])) {
        scanf("%u %u", &low, &high);

        for (total = 0; high % block_length && high >= low; high--)
            if (left_greater[high] < low)
                total += items[high] * (high - low + 1);
            else {
                others = arg_max(count + 1, log2_limit, max, items, low, high);
                total += end_sums[high] - end_sums[others] + items[others] * (others - low + 1);
            }

        for (; (low % block_length) != 1 && low <= high; low++)
            if (right_greater[low] > high)
                total += items[low] * (high - low + 1);
            else {
                others = arg_max(count + 1, log2_limit, max, items, low, high);
                total += start_sums[low] - start_sums[others] + items[others] * (high - others + 1);
            }
    }

    return 0;
}

1 thought on “HackerRank Sum of the Maximums problem solution”

Comments are closed.