HackerEarth Shil and Wave sequence problem solution

In this HackerEarth Shil and Wave sequence problem solution we have given a sequence A1 , A2 , A3 .. AN of length N . Find total number of wave subsequences having length greater than 1.

Wave subsequence of sequence A1 , A2 , A3 .. AN is defined as a set of integers i1 , i2 .. ik such that Ai1 < Ai2 > Ai3 < Ai4 …. or Ai1 > Ai2 < Ai3 > Ai4 …. and i1 < i2 < …< ik.Two subsequences i1 , i2 .. ik and j1 , j2 .. jm are considered different if k != m or there exists some index l such that il ! = jl.

HackerEarth Shil and Wave sequence problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define inf 1e8

#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
#define mp make_pair
#define pb push_back
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)

ll bt[100011][2]={0};
ll a[100011];
ll bt1[100011]={0};

void update(int ind ,ll val,int pos){
    while(ind<=100000){
        bt[ind][pos]+=val;
        bt[ind][pos]%=mod;
        ind+=(ind&-ind);
    }
}

ll query(int ind,int pos){
    ll ans=0;
    while(ind>0){
        ans+=bt[ind][pos];
        ans%=mod;
        ind-=(ind&-ind);
    }
    return ans;
}

void update1(int ind ,ll val){
    while(ind<=100000){
        bt1[ind]+=val;
        ind+=(ind&-ind);
    }
}

ll query1(int ind){
    ll ans=0;
    while(ind>0){
        ans+=bt1[ind];
        ind-=(ind&-ind);
    }
    return ans;
}

int main(){
    freopen("input-15.txt","r",stdin);
    freopen("output-15.txt","w",stdout);

    int N;
    cin >> N;
    rep(i,N){
        cin >> a[i+1];
    }
    ll ans=0;
    ll f,s;
    for(int i=1;i<=N;i++){
        
        f=query(a[i]-1,1);
        s=query(100000,0)-query(a[i],0);
        s+=mod;
        s%=mod;

        f+=query1(a[i]-1);
        s=s+query1(100000)-query1(a[i]);
        
        f%=mod;
        s%=mod;
        
        update1(a[i],1);
        update(a[i],f,0);
        update(a[i],s,1);
        
        ans=ans+f+s;
        ans%=mod;
        
    }
    cout<<ans;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define max 100002
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
ll tree[max][3];

ll read(ll idx, ll i) {
    ll sum = 0;
    while (idx > 0) {
        sum += tree[idx][i];
        if(sum > mod) sum %= mod;
        idx -= (idx & -idx);
    }
    return sum;
}
void update(ll idx ,ll val, ll i) {
    while (idx <= max) {
        tree[idx][i] += val;
        if(tree[idx][i] > mod) tree[idx][i] %= mod;
        idx += (idx & -idx);
    }
}
int main() 
{
    ll n,i,j;
    cin>>n;
    ll a[n];
    for(i = 0; i < n; i++) {
        cin>>a[i];
    }
    if(n == 1) {
        puts("0");
        return 0;
    }
    memset(tree,0,sizeof(tree));
    ll ans = 0;
    update(a[0],1,0);
    update(a[0],0,1);
    update(a[0],0,2);
    for(i = 1; i < n; i++) {
        ll x,y;
        x = (read(a[i]-1,1) + read(a[i]-1,0))%mod;
        y = (read(max-1,2) - read(a[i],2) + read(max-1,0) - read(a[i],0) + mod)%mod;
        ans = (ans + x + y)%mod;
        update(a[i],y,1);
        update(a[i],x,2);
        update(a[i],1,0);
    }
    cout<<ans<<endl;
    return 0;
}