List the sub arrays

QUESTION

You are given an array A of size N. Let us list down all the subarrays of the given array. There will be a total of N * (N + 1) / 2 subarrays of the given array. Let us sort each of the subarrays in descending order of the numbers in it.\n\nNow you want to sort these subarrays in descending order. You can compare two subarrays B, C, as follows.\n\n\n compare(B, C):\n Append N – |B| zeros at the end of the array B.\n Append N – |C| zeros at the end of the array C.\n for i = 1 to N:\n if B[i] < C[i]:\n return B is less than C\n if B[i] > C[i]:\n return B is greater than C\n return B and C are equal.\n\nYou are given M queries asking for the maximum element in the pth subarray (1-based indexing).\n\nInput\n\nThe first line of input contains T, the number of test cases.\n\nThe first line of each test case contains two space separated integers N and M, denoting the array size and the number of queries respectively.\n\nThe next line contains N space-separated integers denoting the array elements.\n\nEach of the next M lines contains a single integer – p.\n\nOutput\n\nOutput a single integer corresponding to the maximum element in the pth subarray.\n\nConstraints\n\n1 <= Ai <= 10^9\n1 <= p <= N+1C2\n\nSubtasks\n\nSubtask #1 (20 points):\n1<= T <= 20\n1<= N <= 200\n1<= M <= 10^4\n\nSubtask #2 (30 points):\n1 <= T <= 20\n1 <= N <= 3000\n1 <= M <= 10^4\n\nSubtask #3 (50 points):\n1 <= T <= 5\n1<= N <= 10^5\n1<= M <= 10^5\n.

ANSWER

#include <stdio.h>
#include <stdlib.h>
 
#define N 100000
 
struct A {
 int i, a;
 long long k;
} aa[N];
 
int compare(const void *a, const void *b) {
 struct A *pa = (struct A *) a;
 struct A *pb = (struct A *) b;
 
 return pa->a - pb->a;
}
 
int binsearch(struct A *aa, int n, long long x) {
 int l = -1, r = n - 1;
 
 while (r - l > 1) {
  int m = (l + r) / 2;
 
  if (aa[m].k >= x)
   r = m;
  else
   l = m;
 }
 return r;
}
 
int ll[N], dsu[N], used[N];
 
int find(int x) {
 return dsu[x] < 0 ? x : (dsu[x] = find(dsu[x]));
}
 
void join(int x, int y) {
 x = find(x);
 y = find(y);
 if (x == y)
  return;
 if (dsu[x] < dsu[y])
  dsu[y] = x;
 else if (dsu[x] > dsu[y])
  dsu[x] = y;
 else {
  dsu[x]--;
  dsu[y] = x;
 }
}
 
long long count(int l) {
 return (long long) l * (l + 1) / 2;
}
 
long long join_(int x, int y) {
 int lx, ly, l; 
 
 x = find(x);
 y = find(y);
 lx = ll[x];
 ly = ll[y];
 l = ll[x] = ll[y] = (ll[x] + ll[y]);
 join(x, y);
 return count(l) - count(lx) - count(ly);
}
 
int main() {
 int t;
 
 scanf("%d", &t);
 while (t-- > 0) {
  int i, n, m;
  long long k, cnt;
 
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
   scanf("%d", &aa[i].a);
   aa[i].i = i;
  }
  qsort(aa, n, sizeof(*aa), compare);
  for (i = 0; i < n; i++) {
   dsu[i] = -1;
   ll[i] = 0;
  }
  k = 0;
  for (i = 0; i < n; i++) {
   int j = aa[i].i;
 
   k += 1;
   ll[j] = 1;
   if (j - 1 >= 0 && ll[j - 1] > 0)
    k += join_(j, j - 1);
   if (j + 1 < n && ll[j + 1] > 0)
    k += join_(j, j + 1);
   aa[i].k = k;
  }
  cnt = count(n);
  while (m-- > 0) {
   long long p;
 
   scanf("%lld", &p);
   i = binsearch(aa, n, cnt - p + 1);
   printf("%d\n", aa[i].a);
  }
 }
 return 0;
}
 
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.