[Devskill] DCP-19: Multiplication Interval

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DCP-19: Multiplication Interval
Source            : Devskill
Category          : Data Structure
Algorithm         : Sparse Table
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
using pii = pair <int, int>;
 
static const int mx = 1e5+5;
 
int A[mx];
int ST[20][mx];
 
inline void computeST(int N)
{
      for (int i = 0; i < N; i++) ST[0][i] = i;
      for (int k = 1; (1<<k) < N; k++)
      {
            for (int i = 0; i + (1<<k) <= N; i++)
            {
                  int x = ST[k-1][i];
                  int y = ST[k-1][i+(1<<(k-1))];
                  ST[k][i] = A[x] <= A[y] ? x : y;
            }
      }
}
 
inline pii conOne(int s, int e)
{
      int sum = 0;
      int cnt = 0;
      int start = s;
      int endd = s;
      int fStart = s;
      int fEnd = s;
      for (int i = s; i <= e; i++)
      {
            if (A[i] != 1 && cnt == 0) continue;
            if (A[i] == 1 && i!=e)
            {
                  if (cnt == 0) start = i;
                  cnt++;
            }
            else if (A[i] != 1 || i == e)
            {
                  endd = i-1;
                  if (A[i] == 1) endd = i;
                  if (i && A[i-1] != 1) start = i;
                  if (endd - start + 1 > sum)
                  {
                        sum = endd-start+1;
                        fStart = start;
                        fEnd = endd;
                  }
                  cnt = 0;
            }
      }
      return pii(fStart, fEnd);
}
 
inline int RMQ(int i, int j)
{
      int k = log2(j - i);
      int x = ST[k][i];
      int y = ST[k][j - (1<<k) + 1];
      return A[x] <= A[y] ? x : y;
}
 
int main()
{
//    freopen("in.txt", "r", stdin);
 
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int N, Q;
            scanf("%d %d", &N, &Q);
            for (int i = 0; i < N; i++) scanf("%d", &A[i]);
            computeST(N);
            printf("Case %d:\n", tcase);
            while (Q--)
            {
                  int x, y;
                  scanf("%d %d", &x, &y);
                  x -= 1;
                  y -= 1;
                  if (x == y)
                  {
                        printf("%d %d %d\n", A[x], x+1, y+1);
                        continue;
                  }
                  int id = RMQ(x, y);
                  int mini = A[id];
                  if (mini == 0)
                  {
                        printf("%d %d %d\n", mini, x+1, y+1);
                  }
                  else if (mini == 1)
                  {
                        pii p = conOne(x, y);
                        printf("%d %d %d\n", mini, p.first+1, p.second+1);
                  }
                  else
                  {
                        printf("%d %d %d\n", mini, id+1, id+1);
                  }
            }
      }
      return 0;
}