Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Delete a Subarray CodeChef Solution
Problem -Delete a 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.
Delete a Subarray CodeChef Solution in C++14
#include <bits/stdc++.h>
using namespace std;
#ifdef PRADEEP
#include "dbg.h"
#else
#define dbg(x...)
#endif
using ll = long long;
ostream& operator<<(ostream& os,const vector<int>& x) {
for (const int& i : x) { os << i << ' '; }
return os;
}
ostream& operator<<(ostream& os,const vector<double>& x) {
for (const double& i : x) { os << setprecision(17) << i << ' '; }
return os;
}
template <typename T>
void print(int t,const T& x) {
cout << "Case #" << t << ": " << fixed << setprecision(10) << x << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int t = 1;t <= T;t++) {
int n;
cin >> n;
vector<ll> a(n + 2);
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
a[0] = -1e16; a[n + 1] = 1e16;
ll ans = 0;
vector<ll> sfx(n + 2,0);
vector<ll> pfx(n + 2,0);
pfx[1] = 1;
for (int i = 2;i <= n;i++) {
if (a[i] <= a[i - 1]) break ;
pfx[i] = 1;
}
sfx[n] = 1;
for (int i = n - 1;i >= 1;i--) {
if (a[i] >= a[i + 1]) break ;
sfx[i] = 1;
}
vector<ll> s;
s.push_back(-1e16);
dbg(pfx, sfx);
for (int i = 1;i < n;i++) {
if (sfx[i + 1]) {
int d = lower_bound(s.begin(), s.end(), a[i + 1]) - s.begin();
dbg(i, d);
ans += d;
}
if (pfx[i]) {
s.push_back(a[i]);
}
}
ans += s.size() - 1;
cout << ans << '\n';
}
return 0;
}Delete a Subarray CodeChef Solution in PYTH 3
# cook your dish here
import bisect
def pre(a):
for p in range(n-1):
if(a[p]>=a[p+1]):
return p
return n-1
def suf(a):
for s in range(1,n):
if(a[n-s]<=a[n-s-1]):
return n-s
return 0
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
p=pre(a)
s=suf(a)
b=a[s:n]
count=0
for i in range(p+1):
k=bisect.bisect(b,a[i])
k+=s
count+=n-k+1
if(s==0):
print((n*(n+1))//2-1)
else:
print(count+n-s)
Delete a Subarray CodeChef Solution in C
#include <stdio.h>
int main(void) {
int t;
scanf("%d",&t);
while(t--){
long long int n,i,j,k;
scanf("%lld",&n);
long long int a[n],count=1,ans=1;
for(i=0;i<n;i++) scanf("%lld",&a[i]);
if(n==1){
printf("0\n");
continue;
}
for(j=0;j<n-2 && a[j+1]>a[j];j++) count++;
for(j=n-1;j>1 && a[j-1]<a[j]; j--) count++;
ans+=count;
if(a[0]<a[n-1]){
j=0; k=n-1;
while(k>2 && a[k-1]<a[k] && a[k-1]>a[0]) k--;
count = n-k;
ans +=count;
while(k<n){
j++;
if(a[j]<=a[j-1]) break;
if(k<=j+1) k=j+2;
while(k<n && a[k]<=a[j]) k++;
count=n-k;
ans+=count;
}
}
printf("%lld\n",ans);
}
return 0;
}Delete a Subarray CodeChef Solution in JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
class Main {
private static final int MOD = 1000000009;
public static void main(String[] args) throws IOException {
ReadIO scan = new ReadIO(System.in);
int T = scan.nextInt();
while (T-- > 0) {
int N = scan.nextInt();
long[] arr = new long[N];
scan.fillLongArray(arr);
if(N==1){
System.out.println(0);
continue;
}
else if(N==2){
System.out.println(2);
continue;
}
boolean[] prefix = new boolean[N];
boolean[] suffix = new boolean[N];
Arrays.fill(prefix, true);
Arrays.fill(suffix, true);
int searchStart = N-1;
for (int i = 1, j = N - 2; i < N && j >= 0; i++, j--) {
prefix[i] = prefix[i - 1] && (arr[i - 1] < arr[i]);
suffix[j] = suffix[j + 1] && (arr[j + 1] > arr[j]);
if(suffix[j]){
searchStart = j;
}
}
if(prefix[N-1]){
long temp = N;
System.out.println((temp*(temp+1))/2 -1);
continue;
}
long count = 0L;
for (int i = 0; i <N; i++) {
if(prefix[i]){
int j = Arrays.binarySearch(arr,searchStart,N,arr[i]);
// if negative adjust position
j = j<0?-(j+1):j+1; // here j+1 if handle if arr[i]== an element in suffix sub array
count+=N-j+1;
}
}
System.out.println(count+N-searchStart);
}
}
static class ReadIO {
private final BufferedReader br;
StringTokenizer stringTokenizer;
public ReadIO(InputStream inputStream) {
this.br = new BufferedReader(new InputStreamReader(inputStream));
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public String next() throws IOException {
if (stringTokenizer == null || !stringTokenizer.hasMoreElements())
stringTokenizer = new StringTokenizer(br.readLine());
return stringTokenizer.nextToken();
}
public String nextLine() throws IOException {
return br.readLine();
}
public void close() throws IOException {
br.close();
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public void fillIntArray(int[] arr) throws IOException {
for (int i = 0; i < arr.length; i++) {
arr[i] = nextInt();
}
}
public void fillLongArray(long[] arr) throws IOException {
for (int i = 0; i < arr.length; i++) {
arr[i] = nextLong();
}
}
public void fill2DArray(int[][] arr) throws IOException {
for (int i = 0; i < arr.length; i++) {
fillIntArray(arr[i]);
}
}
}
}Delete a Subarray CodeChef Solution in PYPY 3
# cook your dish here
import bisect
def pre(a):
for p in range(n-1):
if(a[p]>=a[p+1]):
return p
return n-1
def suf(a):
for s in range(1,n):
if(a[n-s]<=a[n-s-1]):
return n-s
return 0
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
p=pre(a)
s=suf(a)
b=a[s:n]
count=0
for i in range(p+1):
k=bisect.bisect(b,a[i])
k+=s
count+=n-k+1
if(s==0):
print((n*(n+1))//2-1)
else:
print(count+n-s)Delete a Subarray CodeChef Solution in PYTH
import sys
for i in range(input()):
n=input()
m=map(int,raw_input().split())
if n==1:
print 0
elif n==2:
print 2
else:
len1,len2=1,1
k1=1
k2=-1
while k1<n:
if m[k1]>m[k1-1]:
len1+=1
else:
break
k1+=1
while k2>((-1)*n):
if m[k2]>m[k2-1]:
len2+=1
else:
break
k2-=1
if len1==len2 and len2==n:
print ((n*(n+1))/2-1)
else:
left=len1-1
right=n-len2
a=m[:len1]
b=m[right:]
k=0
ans=0
c=len(b)
for j in range(len1):
while k<len(b):
if b[k]<=a[j]:
k+=1
else:
break
ans+=(len2-k+1)
print ans+len2
Delete a Subarray CodeChef Solution in C#
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class TEST{
static void Main(){
Sol mySol =new Sol();
mySol.Solve();
}
}
class Sol{
public void Solve(){
for(;T>0;T--){
N = ri();
A = rla();
List<long> L = new List<long>();
L.Add(A[0]);
for(int i=1;i<N;i++){
if(A[i] <= L[L.Count - 1]) break;
L.Add(A[i]);
}
List<long> R = new List<long>();
R.Add(A[N-1]);
for(int i=N-2;i>=0;i--){
if(A[i] >= R[R.Count - 1]) break;
R.Add(A[i]);
}
R.Reverse();
if(L.Count == N){
Console.WriteLine((long) N * (long)(N + 1) / 2 - 1);
continue;
}
long tot = 0;
int r = 0;
for(int i=0;i<L.Count;i++){
if(i == 0){
tot += R.Count;
//Console.WriteLine(tot);
continue;
}
while(r < R.Count && R[r] <= L[i-1]) r++;
tot += R.Count - r + 1;
//Console.WriteLine(tot);
}
int rr = 0;
while(rr < R.Count && R[rr] <= L[L.Count - 1]) rr++;
tot += R.Count - rr + 1;
//Console.WriteLine(tot);
Console.WriteLine(tot);
}
}
int N;
long[] A;
int T;
public Sol(){
T = ri();
}
static String rs(){return Console.ReadLine();}
static int ri(){return int.Parse(Console.ReadLine());}
static long rl(){return long.Parse(Console.ReadLine());}
static double rd(){return double.Parse(Console.ReadLine());}
static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}Delete a Subarray CodeChef Solution Review:
In our experience, we suggest you solve this Delete a 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 Delete a Subarray CodeChef Solution.
Conclusion:
I hope this Delete a 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!
