oj.uz

답안 #871067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871067 2023-11-09T19:55:56 Z Pekiban Bitaro's travel (JOI23_travel) C++17
0 / 100
 4 ms 31324 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int mxN = 2e5+2, LOG = 20;
    int mx[LOG][mxN], mn[LOG][mxN], lg[mxN];
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        lg[1] = 0;
        for (int i = 2; i < mxN; ++i) {
            lg[i] = lg[i/2]+1;
        }
        int n;
        cin >> n;
        int a[n+2]; set<pair<int, int>> s;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            s.insert({a[i], i});    
        }
        for (int i = 1; i <= n; ++i) {
            if (i != 1) mx[0][i] = 2*a[i] - a[i-1];
            if (i != n) mn[0][i] = 2*a[i] - a[i+1];
        }
        for (int i = 1; i < LOG; ++i) {
            for (int j = 1; j <= n; ++j) {
                mx[i][j] = max(mx[i-1][j], mx[i-1][j + (1 << (i - 1))]);
                mn[i][j] = min(mn[i-1][j], mn[i-1][j + (1 << (i - 1))]);
            }
        }
        auto mnq = [&](int l, int r) {
            return min(mn[lg[r-l+1]][l], mn[lg[r-l+1]][r-(1 << (r-l+1))]);
        };
        auto mxq = [&](int l, int r) {
            return max(mx[lg[r-l+1]][l], mx[lg[r-l+1]][r-(1 << (r-l+1))]);
        };
        int q;
        cin >> q;
        while (q--) {
            int x;
            cin >> x;
            auto it = s.lower_bound({x, 0});
            int b = 0;
            if (it != s.end()) {
                b = (*it).second;
                if (abs(x-a[b]) > abs(x-a[b-1]))    b--;
            } 
            if (it == s.end() || (*it).first != 1) {
                b = n;
            }
            long long ans = abs(x-a[b]) + a[n] - a[1]; // verovatno staje u int
            int l = b, r = b; // dir = 1 => idi desno, dir = 0 => idi levo.
            bool dir = (b == 1 ? 1 : (b == n ? 0 : (a[b] - a[b-1] <= a[b+1] - a[b] ? 0 : 1)));
            while (l != 1 && r != n) {
                if (dir) {
                    if (r == n-1 || mnq(r+1, n-1) > a[l-1]) {
                        ans += a[n] - a[l];
                        break;
                    }
                    int le = r+1, ri = n-1, t = 0;
                    while (le <= ri) {
                        int mid = (le + ri)/2;
                        if (mnq(r+1, mid) <= a[l-1]) {
                            t = mid;
                            ri = mid-1;
                        }
                        else {
                            le = mid+1;
                        }
                    }
                    ans += a[t] - a[l];
                    r = t;
                }
                else {
                    if (l == 2 || mxq(2, l-1) <= a[r+1]) {
                        ans += a[r] - a[1];
                        break;
                    }
                    int le = 2, ri = n-1, t = 0;
                    while (le <= ri) {
                        int mid = (le + ri)/2;
                        if (mxq(mid,  l-1) > a[r+1]) {
                            t = mid;
                            le = mid+1;
                        }
                        else {
                            ri = mid-1;
                        }
                    }
                    ans += a[r] - a[t];
                    l = t;
                }
                dir ^= 1;
            }
            cout << ans << '\n';
        }
    }

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 31324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 31324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 31324 KB Output isn't correct
2 Halted 0 ms 0 KB -