Advertisement
Josif_tepe

Untitled

May 23rd, 2024
712
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn  = 2e5 + 10;
  4. typedef long long ll;
  5. int segment_tree[3 * maxn], a[maxn];
  6. int n;
  7. void build_tree(int L, int R, int pos) {
  8.     if(L == R) {
  9.         segment_tree[pos] = L;
  10.     }
  11.     else {
  12.         int middle = (L + R) / 2;
  13.         build_tree(L, middle, 2 * pos);
  14.         build_tree(middle + 1, R, 2 * pos + 1);
  15.         if(a[segment_tree[2 * pos]] > a[segment_tree[2 * pos + 1]]) {
  16.             segment_tree[pos] = segment_tree[2 * pos + 1];
  17.         }
  18.         else {
  19.             segment_tree[pos] = segment_tree[2 * pos];
  20.         }
  21.     }
  22. }
  23. int query(int L, int R, int pos, int i, int j) {
  24.     // L R i L R j L R
  25.     if(R < i or j < L) {
  26.         return -1;
  27.     }
  28.     if(i <= L and R <= j) {
  29.         return segment_tree[pos];
  30.     }
  31.     int middle = (L + R) / 2;
  32.     int q1 = query(L, middle, 2 * pos, i, j);
  33.     int q2 = query(middle + 1, R, 2 * pos + 1, i, j);
  34.     if(q1 == -1) {
  35.         return q2;
  36.     }
  37.     else if(q2 == -1) {
  38.         return q1;
  39.     }
  40.     else if(a[q1] < a[q2]) {
  41.         return q1;
  42.     }
  43.     return q2;
  44.  
  45. }
  46. int rec(int i, int j) {
  47.     int min_idx = query(0, n - 1, 1, i, j);
  48.     int res = a[min_idx] * (j - i + 1);
  49.  
  50.     if(min_idx - 1 >= i) {
  51.         res = max(res, rec(i, min_idx - 1));
  52.     }
  53.     if(min_idx + 1 <= j) {
  54.         res = max(res, rec(min_idx + 1, j));
  55.     }
  56.     return res;
  57. }
  58. int main()
  59. {
  60.     ios_base::sync_with_stdio(false);
  61.     cin >> n;
  62.     for(int i = 0; i < n; i++) {
  63.         cin >> a[i];
  64.     }
  65.     build_tree(0, n - 1, 1);
  66.     cout << rec(0, n - 1) << endl;
  67.     return 0;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement