이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<i64> t(2 * n);
for (int i = 0; i < n; i++) {
std::cin >> t[i + n];
}
i64 ans = 0;
auto update = [&](int l, int r, i64 val) {
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l % 2 == 1) t[l++] += val;
if (r % 2 == 0) t[r--] += val;
}
};
auto a = [&](int p) {
i64 res = 0;
for (p += n; p > 0; p >>= 1) {
res += t[p];
}
return res;
};
for (int l = 1, r = n - 1; l <= r; ) {
while (l < n && a(l) > a(l - 1)) l++;
while (r - 1 >= 0 && a(r - 1) > a(r)) r--;
if (l == r) {
ans++;
break;
}
if (l > r) break;
i64 val = std::min(a(l - 1) + 1 - a(l), a(r) + 1 - a(r - 1));
update(l, r - 1, val);
ans += val;
}
std::cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |