Submission #1113062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113062		duckindog	Real Mountains (CCO23_day1problem2)	C++17	0 / 25	1 ms	476 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10,
          M = 1'000'003,
          MAX = 1'000'000'001;
int n;
int h[N];

int goalH[N];

int f[N << 2];
void build(int s, int l, int r) { 
  if (l == r) { 
    f[s] = h[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  f[s] = min(f[s << 1], f[s << 1 | 1]);
}
void update(int s, int l, int r, int p, int x) { 
  if (p < l || p > r) return;
  if (l == r) { 
    f[s] = x;
    return;
  }
  int mid = (l + r) >> 1;
  update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
  f[s] = min(f[s << 1], f[s << 1 | 1]);
}
int query(int s, int l, int r, int u, int v) { 
  if (v < l || u > r) return MAX;
  if (u <= l && r <= v) return f[s];
  int mid = (l + r) >> 1;
  return min(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> h[i];

  for (int i = 1; i <= n; ++i) { 
    goalH[i] = min(*max_element(h + 1, h + i + 1), 
                    *max_element(h + i, h + n + 1));
  }
  
  long long answer = 0;

  build(1, 1, n);
  for (int height = 1; height <= 100; ++height) { 
    vector<int> vt;
    for (int i = 1; i <= n; ++i) { 
      if (h[i] == height) update(1, 1, n, i, MAX);
      if (h[i] != goalH[i] && h[i] == height) vt.push_back(i);
    }
    
    if (!vt.size()) continue;
    
    if (vt.size() == 1) { 
      int i = vt[0];
      answer += query(1, 1, n, 1, i) + query(1, 1, n, i, n) + h[i];
    } else { 
      int l = vt[0], r = vt.back();

      long long addLFirst = query(1, 1, n, 1, l) + query(1, 1, n, l, n) + 
                            height + 1 + query(1, 1, n, r, n);
      long long addRFirst = query(1, 1, n, 1, r) + query(1, 1, n, r, n) + 
                            height + 1 + query(1, 1, n, 1, l);

      answer += min(addLFirst, addRFirst);
      answer += 1ll * (vt.size() - 2) * (height * 3 + 1);
    }

    for (const auto& i : vt) h[i] = height;
  }

  cout << answer << "\n";
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4