| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1047151 | alex_2008 | Text editor (CEOI24_editor) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
int l[N];
int st[N][21];
int lg2[N];
int mn[N];
void precalc() {
lg2[1] = 0;
for (int i = 2; i < N; i++) {
lg2[i] = lg2[i / 2] + 1;
}
}
int min_in_range(int l, int r) {
int w = lg2[r - l + 1];
return min(st[l][w], st[r - (1 << w) + 1][w]);
}
int main() {
precalc();
int n;
cin >> n;
int sl, sc, el, ec;
cin >> sl >> sc >> el >> ec;
for (int i = 1; i <= n; i++) {
cin >> l[i];
l[i]++;
}
for (int i = n; i >= 1; i--) {
st[i][0] = l[i];
for (int j = 1; j < 20; j++) {
int pos = i + (1 << (j - 1));
st[i][j] = min(st[i][j - 1], st[pos][j - 1]);
}
}
int ans = 1000000000 + n + 10;
for (int i = 1; i <= n; i++) {
int cur = 0;
cur += abs(sl - i);
cur += abs(i - el);
int c = min({ sc, min_in_range(min(i, sl), max(i, sl)), min_in_range(min(i, el), max(i, el)) });
cur += abs(c - ec);
ans = min(ans, cur);
}
for (int i = 1; i <= n; i++) {
mn[i] = abs(sl - i) + min(min_in_range(min(i, sl), max(i, sl)), sc) - 1;
if (i > 1) {
mn[i] = min(mn[i], abs(sl - (i - 1)) + l[i - 1] + 1 - min(sc, min_in_range(min(i - 1, sl), max(i - 1, sl))));
}
}
for (int i = 2; i <= n; i++) {
mn[i] = min(mn[i], mn[i - 1] + 1);
}
for (int i = n - 1; i >= 1; i--) {
mn[i] = min(mn[i], mn[i + 1] + 1);
}
ans = min(ans, mn[el] + ec - 1);
for (int i = 2; i <= n; i++) {
//(i - 1, l[i])
int cur = mn[i] + 1;
cur += abs(el - (i - 1));
int c = min_in_range(min(i - 1, el), max(i - 1, el));
cur += abs(c - ec);
ans = min(ans, cur);
}
cout << ans << "\n";
}