Society Control

#Problem link:
[Practice] CENV004 Problem - CodeChef
[Codennovate] CodeChef: Practical coding for everyone

Author: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef
Editorialist: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef

DIFFICULTY: Medium
# PREREQUISITES: Math

Solution To The Problem

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mod 1000000007
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,start,end) for(int i=start; i<=end; i++)
#define repd(i,start,end) for(int i=start; i>=end; iā€“)
#define all(x) x.begin(),x.end()

void solve() {
int n;
cin >> n;
int f[n];
rep(i,n)
cin >> f[i];

vector control(n,0);
vector left(n);
vector right(n);

left[0] = -1;
for(int i=1; i<n; i++) {
int j=i-1;
while(j>=0 && f[j]<f[i])
j = left[j];
left[i] = j;
}

right[n-1] = n;
for(int i=n-2; i>=0; iā€“) {
int j=i+1;
while(j<n && f[j]<f[i])
j = right[j];
right[i] = j;
}

rep(i,n) {
control[i] = (right[i]-i)*(i-left[i]);
cout << control[i] << " ";
}

cout << ā€œ\nā€;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}