Advertisement
Guest User

Untitled

a guest
Jul 21st, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll a[2000012], dp[2110000], dp1[2000101];
  5. int main() {
  6. stack <ll> q, q1;
  7. int n;
  8. cin >> n;
  9. for (int i = 0; i < n; i++) {
  10. cin >> a[i];
  11. }
  12. for (int i=0; i < n; i++) {
  13. if (q.size() == 0) {
  14. q.push(i);
  15. continue;
  16. }
  17. while (!q.empty()) {
  18. if (a[q.top()] < a[i]) {
  19. break;
  20. }
  21. q.pop();
  22. }
  23. if (q.empty()) {
  24. dp[i] = i;
  25. }
  26. if (!q.empty())
  27. dp[i] = i - q.top() - 1;
  28. q.push(i);
  29. }
  30. for (int i = n - 1; i >= 0; i--) {
  31. if (q1.size() == 0) {
  32. q1.push(i);
  33. continue;
  34. }
  35. while (!q1.empty()) {
  36. if (a[q1.top()] < a[i]) {
  37. break;
  38. }
  39. q1.pop();
  40. }
  41. if (q1.empty()) {
  42. dp1[i] = n - i - 1;
  43. }
  44. if (!q1.empty())
  45. dp1[i] = q1.top() - i - 1;
  46. q1.push(i);
  47. }
  48. ll area = -1, l, r;
  49. for (int i = 0; i < n; i++) {
  50. if (area < a[i]) {
  51. area = a[i];
  52. l = i;
  53. r = i;
  54. }
  55. int l1 = i - dp[i], r1 = dp1[i] + i;
  56. if (area < (dp[i] + dp1[i] + 1) * a[i]) {
  57. area = (dp[i] + dp1[i] + 1) * a[i];
  58. l = i - dp[i];
  59. r = i + dp1[i];
  60. }
  61. }
  62. cout << area << endl << l + 1 << ' ' << r + 1;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement