#include "meetings.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define pb push_back #define mk make_pair int l,r; stack<pair<int,int> > s; vector<ll> ret; ll a[800005]; std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) { int q = L.size(); for(int i = 0; i < q; i ++) { l = L[i]; r = R[i]; ll sum = 0; ll ans = 1e18; for(int j = l; j <= r; j ++) { sum += H[j]; while(s.size() > 0 && s.top().ff <= H[j]) { int x = s.top().ss; ll val = s.top().ff; if(s.size() > 1) { s.pop(); int y = s.top().ss + 1; sum -= (ll) (x - y + 1) * val; sum += (ll) (x - y + 1) * H[j]; } else { int y = l; sum -= (ll) (x - y + 1) * val; sum += (ll) (x - y + 1) * H[j]; s.pop(); } } // s.push({H[j], j}); // value / index a[j] = sum; } // while(s.size() > 0) s.pop(); sum = 0; for(int j = r; j >= l; j --) { sum += H[j]; while(s.size() > 0 && s.top().ff <= H[j]) { int x = s.top().ss; ll val = s.top().ff; if(s.size() > 1) { s.pop(); int y = s.top().ss - 1; sum -= (ll) (y - x + 1) * val; sum += (ll) (y - x + 1) * H[j]; } else { int y = r; sum -= (ll) (y - x + 1) * val; sum += (ll) (y - x + 1) * H[j]; s.pop(); } } // s.push({H[j], j}); // value / index a[j] += sum - H[j]; ans = min(ans,a[j]); } while(s.size() > 0) s.pop(); ret.pb(ans); } return ret; }