Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Kth Max Subarray CodeChef Solution
Problem -Kth Max Subarray CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Kth Max Subarray CodeChef Solution in C++14
#include <bits/stdc++.h>
using namespace std;
#ifdef Azizul
#include "debug.cpp"
#else
#define dbg(x...)
#endif
#define int long long
#define ld long double
#define pb push_back
#define vi vector<int>
#define bitcount(x) (int)__builtin_popcount(x)
#define Lsb(x) (int)__builtin_ctzll(x)
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define Yes cout << "YES\n"
#define No cout << "NO\n"
#define ff first
#define ss second
#define endl "\n"
#define pi acos(-1.0)
#define pii pair<int,int>
#define lcm(a,b) (a/__gcd(a, b)*b)
const int mod = 998244353 ;
const int M = 200005 ;
const int inf = 1LL<<40 ;
vector <int> ans, a(M) ;
int n, m;
inline void solve() {
int n, m;
cin >> n >> m ;
vector <int> a(n+5) ;
for (int i=1;i<=n;++i) cin >> a[i] ;
vector <int> l(n+5), r(n+5) ;
stack <int> s;
s.push(0) ;
a[0] = a[n+1] = inf ;
for (int i=1;i<=n;++i) {
while (a[s.top()] <= a[i]) s.pop() ;
l[i] = i-s.top() ;
s.push(i) ;
}
while (!s.empty()) s.pop() ;
s.push(n+1) ;
for (int i=n;i>=1;i--) {
while (a[s.top()] < a[i]) s.pop() ;
r[i] = s.top()-i ;
s.push(i) ;
}
vector <pii> v;
for (int i=1;i<=n;++i) {
int ll = l[i], rr = r[i];
v.push_back({a[i], ll*rr}) ;
}
sort(all(v), greater<pii>()) ;
vector <int> pref(n) ;
for (int i=0;i<n;++i) {
pref[i] = v[i].ss ;
if (i > 0) pref[i] += pref[i-1] ;
}
while (m--) {
int x; cin >> x ;
int l = 0, r = n-1, ans ;
while (l <= r) {
int m = (l+r)>>1;
if (pref[m] >= x) {
ans = v[m].ff ;
r = m-1;
}
else l = m+1 ;
}
cout << ans << endl;
}
}
signed main()
{
fast ;
int t = 1 ; cin >> t ;
while (t--) solve() ;
return 0 ;
} Kth Max Subarray CodeChef Solution in PYTH 3
# cook your dish here
#!/usr/local/bin/python3
import sys
input = sys.stdin.readline
def _l(x,y):
return x < y
def _le(x,y):
return x <= y
def biggest_prev(a,rng,start,fn):
st = [] # monotonically decreasing stack
ret = [0]*len(a)
for i in rng:
el = a[i]
while (st and fn(a[st[-1]],el)):
st.pop()
if st:
ans = abs(i - st[-1])
else:
ans = abs(i - start)
ret[i] = ans
st.append(i)
return ret
def solve():
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = biggest_prev(a,range(0,n),-1,_l)
c = biggest_prev(a,range(n-1,-1,-1),n,_le)
#print(list(zip(a,b,c)))
d = [[x,y*z] for (x,y,z) in zip(a,b,c)]
d.sort(key=lambda x: -x[0])
for i in range(1,len(d)):
d[i][1] += d[i-1][1]
#print(d)
for _ in range(m):
k = int(input())
ans = 0
if k <= d[0][1]:
ans = d[0][0]
else:
l, r = 0, n
while l < r-1:
mid = (l+r)//2
if d[mid][1] < k:
l = mid
else:
r = mid
ans = d[l+1][0]
print(ans)
def main():
for _ in range(int(input())):
solve()
main()Kth Max Subarray CodeChef Solution in C
#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;
}Kth Max Subarray CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
}
else {
continue;
}
}
buf[cnt++] = (byte)c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0,
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
static boolean check(int x , int arr[] , int l[] , int r[]
, long k)
{
long tot = 0;
for(int i = 0; i < arr.length ; i++)
{
if(arr[i] >= x)
{
tot += (long)(r[i]-i+1)*(long)(i-l[i]+1);
}
}
// System.out.println(tot + " " + k);
if(tot >= k)
return true;
return false;
}
public static void main (String[] args) throws java.lang.Exception
{
Reader sc = new Reader();
int t = sc.nextInt();
StringBuffer str = new StringBuffer("");
while(t-- > 0)
{
int n = sc.nextInt();
int m = sc.nextInt();
int tmp[] = new int[n];
int arr[] = new int[n];
for(int i = 0 ; i < n ; i++)
{
arr[i] = sc.nextInt();
tmp[i] = arr[i];
}
Arrays.sort(tmp);
int l[] = new int[n];
int r[] = new int[n];
Stack<Integer> st = new Stack<Integer>();
for(int i = 0 ; i < n ; i++)
{
while(st.size() > 0 && arr[st.peek()] <= arr[i])
{
r[st.pop()] = i-1;
}
st.push(i);
}
while(st.size() > 0)
{
r[st.pop()] = n-1;
}
for(int i = n-1 ; i >= 0 ; i--)
{
while(st.size() > 0 && arr[st.peek()] < arr[i])
{
l[st.pop()] = i+1;
}
st.push(i);
}
while(st.size() > 0)
{
l[st.pop()] = 0;
}
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0 ; i < n ; i++)
{
map.put(tmp[i],i);
}
ArrayList<Integer> ls[] = new ArrayList[n];
for(int i = 0 ; i < n ; i++)
{
ls[i] = new ArrayList<Integer>();
}
for(int i = 0 ; i < n ; i++)
{
ls[map.get(arr[i])].add(i);
}
TreeMap<Long,Integer> mp = new TreeMap<Long,Integer>();
long tot = 0;
for(int i = n-1 ; i >= 0 ; i--)
{
for(Integer j : ls[i])
{
tot += (long)(j-l[j]+1)*(long)(r[j]-j+1);
}
mp.put(tot,tmp[i]);;
}
while(m-- > 0)
{
long k = sc.nextLong();
str.append(mp.get(mp.higherKey(k-1)));
str.append(System.lineSeparator());
}
}
System.out.println(str);
}
}Kth Max Subarray CodeChef Solution in PYPY 3
#!/usr/local/bin/python3
import sys
input = sys.stdin.readline
def _l(x,y):
return x < y
def _le(x,y):
return x <= y
def biggest_prev(a,rng,start,fn):
st = [] # monotonically decreasing stack
ret = [0]*len(a)
for i in rng:
el = a[i]
while (st and fn(a[st[-1]],el)):
st.pop()
if st:
ans = abs(i - st[-1])
else:
ans = abs(i - start)
ret[i] = ans
st.append(i)
return ret
def solve():
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = biggest_prev(a,range(0,n),-1,_l)
c = biggest_prev(a,range(n-1,-1,-1),n,_le)
#print(list(zip(a,b,c)))
d = [[x,y*z] for (x,y,z) in zip(a,b,c)]
d.sort(key=lambda x: -x[0])
for i in range(1,len(d)):
d[i][1] += d[i-1][1]
#print(d)
for _ in range(m):
k = int(input())
ans = 0
if k <= d[0][1]:
ans = d[0][0]
else:
l, r = 0, n
while l < r-1:
mid = (l+r)//2
if d[mid][1] < k:
l = mid
else:
r = mid
ans = d[l+1][0]
print(ans)
def main():
for _ in range(int(input())):
solve()
main()Kth Max Subarray CodeChef Solution in PYTH
import bisect
def right(arr, n):
st = [0]*n
a = [0]*n
index = 0
for i in xrange(1, n):
while (index >= 0 and arr[i] > arr[st[index]]):
index -= 1
a[i] = i if index < 0 else (i - st[index] - 1)
index += 1
st[index] = i
return a
def left(arr1, n):
arr = [0]*n
for i in xrange(n):
arr[i] = arr1[n - i - 1]
st = [0]*n
a = [1]*n
index = 0
for i in xrange(1, n):
while (index >= 0 and arr[i] >= arr[st[index]]):
index -= 1
a[i] = i + 1 if index < 0 else (i - st[index])
index += 1
st[index] = i
a.reverse()
return a
# def left(arr, n):
#
# st = [0]*n
# a = [1]*n
# index = 0
# st[0] = n - 1
# for i in xrange(n - 2, -1 , -1):
# while (index >= 0 and arr[i] >= arr[st[index]]):
# index -= 1
#
# a[i] = i + 1 if index < 0 else (i - st[index])
# index += 1
# st[index] = i
#
# a.reverse()
# return a
tt = int(raw_input())
for i in xrange(tt):
n, m = map(int, raw_input().split())
num = map(int, raw_input().split())
query = []
for j in xrange(m):
query.append(int(raw_input()))
rig = right(num, n)
lef = left(num, n)
temp = [0]*n
for j in xrange(n):
temp[j] = lef[j]*rig[j] + lef[j]
# print temp
ab = zip(num, temp)
ab.sort(reverse = True)
# num, temp = zip(*reversed(sorted(zip(num, temp))))
num, temp = zip(*ab)
accumulate = [0]*n
accumulate[0] = temp[0]
for j in xrange(1, n):
accumulate[j] = accumulate[j-1] + temp[j]
# print num, temp, accumulate
for j in xrange(m):
print num[bisect.bisect_left(accumulate, query[j])]Kth Max Subarray CodeChef Solution Review:
In our experience, we suggest you solve this Kth Max Subarray CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Kth Max Subarray CodeChef Solution.
Conclusion:
I hope this Kth Max Subarray CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
