oj.uz

답안 #1113062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113062 2024-11-15T15:34:12 Z duckindog Real Mountains (CCO23_day1problem2) C++17
0 / 25
 1 ms 476 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 476 KB Output isn't correct
3 Halted 0 ms 0 KB -