PROBLEM LINK(s): Statement
| //ltc.groverkss (Kunwar Shaanjeet Singh Grover) | |
| //IIIT Hyderabad | |
| // Mehul Mathur randi hain | |
| #include <iostream> | |
| #include <iterator> | |
| #include <cstdlib> | |
| #include <algorithm> | |
| #include <stack> | |
| #include <deque> | |
| #include <queue> | |
| #include <vector> | |
| #include <utility> | |
| using namespace std; | |
| #define ll long long | |
| #define ld long double | |
| typedef pair<ll,ll> ii; | |
| typedef vector<ll> vi; // Vector of long long | |
| typedef vector<vi> vvi; // Vector of vi | |
| typedef vector<ii> vii; // Vector of pairs | |
| #define pq priority_queue // Max heap (To convert to min heap, use negative sign before every value) | |
| #define ff first // For pairs | |
| #define ss second // For pairs | |
| #define pb push_back // Pushback to vector | |
| #define mp make_pair // Makes pairs to be stored as pair | |
| #define all(c) (c).begin(), (c).end() // Mainly used by me in sorting | |
| // ordered_set adds two new functions to set - (set).find_by_order([kth element based on zero indexing]) and order_of_key() | |
| // order_of_key returns number of elements less that parameter. If element exists, that order is its index | |
| #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> | |
| int main(void) | |
| { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| ll n; | |
| cin >> n; | |
| ll arr[n]; | |
| for (int i = 0; i < n; i++) | |
| cin >> arr[i]; | |
| stack<ii> s; | |
| vi post(n, n); | |
| for (int i = 0; i < n; i++) | |
| { | |
| while(!s.empty() && arr[i] > s.top().ff) | |
| { | |
| auto p = s.top(); | |
| s.pop(); | |
| post[p.ss] = i; | |
| } | |
| s.push({arr[i], i}); | |
| } | |
| stack<ii> g; | |
| vi pre(n, -1); | |
| for (int i = n - 1; i >= 0; i--) | |
| { | |
| while(!g.empty() && arr[i] >= g.top().ff) | |
| { | |
| auto p = g.top(); | |
| g.pop(); | |
| pre[p.ss] = i; | |
| } | |
| g.push({arr[i], i}); | |
| } | |
| ll cost = 0; | |
| for (int i = 0; i < n; i++) | |
| cost += arr[i] * (i - pre[i]) * (post[i] - i); | |
| ll c = *max_element(arr, arr + n); | |
| for (int i = 0; i < n; i++) | |
| arr[i] = c - arr[i]; | |
| stack<ii> sb; | |
| vi postb(n, n); | |
| for (int i = 0; i < n; i++) | |
| { | |
| while(!sb.empty() && arr[i] > sb.top().ff) | |
| { | |
| auto p = sb.top(); | |
| sb.pop(); | |
| postb[p.ss] = i; | |
| } | |
| sb.push({arr[i], i}); | |
| } | |
| stack<ii> gb; | |
| vi preb(n, -1); | |
| for (int i = n - 1; i >= 0; i--) | |
| { | |
| while(!gb.empty() && arr[i] >= gb.top().ff) | |
| { | |
| auto p = gb.top(); | |
| gb.pop(); | |
| preb[p.ss] = i; | |
| } | |
| gb.push({arr[i], i}); | |
| } | |
| for (int i = 0; i < n; i++) | |
| cost -= (c - arr[i]) * (i - preb[i]) * (postb[i] - i); | |
| cout << cost << "\n"; | |
| } |