Morgan Stanley |OA| SDE -1 | Set-8 | CTC -23LPA| 2024

Question

Answer 1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

 

vector<int> next_greater_element(vector<int>& vec){

stack<int> st;

int n = vec.size();

st.push(-1);

vector<int> res(n);

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

while(st.top()!=-1 && vec[i] >= vec[st.top()]) st.pop();

res[i] = st.top();

st.push(i);

}

return res;

}

 

vector<int> next_smaller_element(vector<int>& vec){

stack<int> st;

int n = vec.size();

st.push(-1);

vector<int> res(n);

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

while(st.top()!=-1 && vec[i] <= vec[st.top()]) st.pop();

res[i] = st.top();

st.push(i);

}

return res;

}

 

void solve(){

int n;

cin >> n;

vector<int> weight(n);

for(int i=0;i<n;i++){

cin >> weight[i];

}

vector<int> next_greater = next_greater_element(weight);

vector<int> next_smaller = next_smaller_element(weight);

int ans = 0;

for(int i=0;i<n;i++){

if(next_greater[i] == -1){

//if all chairs in right are smaller

ans += 15;

}

else if(next_smaller[next_greater[i]]== -1){

//if next greater chair have no smaller chair in right

ans += 10;

}

else{

//otherwise

ans += 5;

}

}

cout << ans << endl;

}

 

int main(){

ll t = 1;

while(t--){

solve();

}

return 0;

}