Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- ll a[2000012], dp[2110000], dp1[2000101];
- int main() {
- stack <ll> q, q1;
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- for (int i=0; i < n; i++) {
- if (q.size() == 0) {
- q.push(i);
- continue;
- }
- while (!q.empty()) {
- if (a[q.top()] < a[i]) {
- break;
- }
- q.pop();
- }
- if (q.empty()) {
- dp[i] = i;
- }
- if (!q.empty())
- dp[i] = i - q.top() - 1;
- q.push(i);
- }
- for (int i = n - 1; i >= 0; i--) {
- if (q1.size() == 0) {
- q1.push(i);
- continue;
- }
- while (!q1.empty()) {
- if (a[q1.top()] < a[i]) {
- break;
- }
- q1.pop();
- }
- if (q1.empty()) {
- dp1[i] = n - i - 1;
- }
- if (!q1.empty())
- dp1[i] = q1.top() - i - 1;
- q1.push(i);
- }
- ll area = -1, l, r;
- for (int i = 0; i < n; i++) {
- int l1 = i - dp[i], r1 = dp1[i] + i;
- if (area < (dp[i] + dp1[i] + 1) * a[i]
- || area == (dp[i] + dp1[i] + 1) * a[i] && r - l +1 >r1 - l1 + 1) {
- area = (dp[i] + dp1[i] + 1) * a[i];
- l = i - dp[i];
- r = i + dp1[i];
- }
- if (area <= a[i]) {
- area = a[i];
- l = i;
- r = i;
- }
- }
- cout << area << endl << l + 1 << ' ' << r + 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement