Perfect Quadruples

Description:

Chang was not able to sleep well last night as he was thinking about a problem which still remains unsolved. Since he has only a day left to solve this problem and hand it to the interviewer, you being his friend decide to help him solve this so that he can clear this round and get a much-needed job. The problem is as follows. Given a list L of N integers, Chang defines a perfect quadruple (i, j, k, l) such that: i, j, k, l are the indices of the list i<= j

Program :

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#define DO long double

#define pb push_back

#define pfr push_front

#define eb emplace_back

#define ef emplace_front

#define gc getchar_unlocked

#define fi first

#define se second

#define pii pair<int,int>

#define pll pair<ll,ll>

#define mp make_pair

#define vi vector<int>

#define vll vector<ll>

#define MOD 1000000007


#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

vector<string> split(const string& s, char c) {

vector<string> v;

stringstream ss(s);

string x;

while (getline(ss, x, c))

v.emplace_back(x);

return move(v);

}

void err(vector<string>::iterator it) {}

template<typename T, typename... Args>

void err(vector<string>::iterator it, T a, Args... args) {

cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';

err(++it, args...);

}


pii ne[4]={mp(0,1), mp(1,0), mp(-1,0), mp(0,-1)};


inline int in() {

    int NR=0,sign=1;   char c=gc();

    while( c < 48 || c > 57 ){if(c=='-')sign=0; c=gc();}

    while(c>47 && c< 58)

    {   NR = (NR << 3) + (NR << 1) + (c - 48);   c=gc();   }

    return (sign?NR:(-NR));

}


const int NMAX = (int)1e6+5, mod = (int)1e9+7;


ll dpmax[NMAX], dpmin[NMAX], cmin[NMAX], a[NMAX];


void setMax(int n){

int i,j,k;

stack<pii> st;

dpmax[1] = a[1];

st.push(mp(a[1], 1));

for(i = 2 ;i <= n; i++){

while(!st.empty() && a[i] > st.top().fi){

st.pop();

}

if(!st.empty()){

pii p = st.top();

dpmax[i] += dpmax[p.se];

dpmax[i] += ((a[i]*(i-p.se))%mod);

}

else{

dpmax[i] = a[i]*i;

}

dpmax[i] %= mod;

st.push(mp(a[i],i));

}

}


void setMin(int n){

int i,j,k;

stack<pii> st;

dpmin[n] = a[n];

st.push(mp(a[n], n));

for(i = n-1 ;i > 0; i--){

while(!st.empty() && a[i] < st.top().fi){

st.pop();

}

if(!st.empty()){

pii p = st.top();

dpmin[i] += dpmin[p.se];

dpmin[i] += ((a[i]*(p.se-i))%mod);

}

else{

dpmin[i] = a[i]*(n-i+1);

}

dpmin[i] %= mod;

st.push(mp(a[i],i));

}

cmin[n] = dpmin[n];

for(i=n-1 ; i>0; i--){

cmin[i] = (dpmin[i] + cmin[i+1])%mod;

}

}


int main(){


int j,k,l,m,n,i;

ll x,y,z;

int t=1;

while(t--){

n=in();

       

for(i=1; i<=n; i++){

      a[i] = in();

          // dpmin[i]=dpmax[i]=cmin[i]=0;

        }

setMin(n);

setMax(n);

x = 0;

for(i=1; i<n; i++){

y = (dpmax[i]*cmin[i+1])%mod;

x = (x+y)%mod;

}

cout<<x<<endl;

}


return 0;

}