이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const ll linf = 1e18;
int l[N][18], r[N][18], logs[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < n; i++) l[i][0] = 2 * a[i] - a[i - 1];
for (int j = 1; j < 18; j++) {
for (int i = 1; i < n - (1 << j) + 1; i++) {
l[i][j] = max(l[i][j - 1], l[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 0; i < n - 1; i++) r[i][0] = 2 * a[i] - a[i + 1];
for (int j = 1; j < 18; j++) {
for (int i = 0; i < n - (1 << j); i++) {
r[i][j] = min(r[i][j - 1], r[i + (1 << (j - 1))][j - 1]);
}
}
int zz = 0;
for (int i = 1; i <= n; i++) {
if ((1 << (zz + 1)) == i) zz += 1;
logs[i] = zz;
}
auto GetLeft = [&] (int p, int q) {
int o = logs[q - p + 1];
return max(l[p][o], l[q - (1 << o) + 1][o]);
};
auto GetRight = [&] (int p, int q) {
int o = logs[q - p + 1];
return min(r[p][o], r[q - (1 << o) + 1][o]);
};
int q; cin >> q;
while (q--) {
int s; cin >> s;
if (s >= a[n - 1]) {
cout << s - a[0] << en;
continue;
}
if (s <= a[0]) {
cout << a[n - 1] - s << en;
continue;
}
int up = (int)(upper_bound(a.begin(), a.end(), s) - a.begin());
int lo = up - 1;
if (a[lo] == s) lo -= 1;
int uu = 0;
ll ans = s;
if (s - a[lo] > a[up] - s) {
uu = 1;
ans = -s;
}
while (1) {
if (uu == 0) {
if (GetLeft(1, lo) <= a[up] || lo <= 0) {
ans += a[n - 1] - 2 * a[0];
cout << ans << en;
break;
}
int lef = 1, rig = lo, gde = -1;
while (lef <= rig) {
int mid = lef + rig >> 1;
if (GetLeft(mid, lo) > a[up]) {
lef = mid + 1;
gde = mid;
}
else rig = mid - 1;
}
ans -= 2 * a[gde];
uu ^= 1;
lo = gde - 1;
up += 1;
continue;
}
if (GetRight(up, n - 2) > a[lo] || up >= n - 1) {
ans += 2 * a[n - 1] - a[0];
cout << ans << en;
break;
}
int lef = up, rig = n - 2, gde = -1;
while (lef <= rig) {
int mid = lef + rig >> 1;
if (GetRight(up, mid) <= a[lo]) {
rig = mid - 1;
gde = mid;
}
else lef = mid + 1;
}
ans += 2 * a[gde];
uu ^= 1;
up = gde + 1;
lo -= 1;
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
travel.cpp: In function 'int main()':
travel.cpp:73:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid = lef + rig >> 1;
| ~~~~^~~~~
travel.cpp:93:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int mid = lef + rig >> 1;
| ~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |