답안 #796022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796022	2023-07-28T04:41:58 Z	이동현(#10071)	Bitaro's travel (JOI23_travel)	C++17	100 / 100	494 ms	126772 KB

travel

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)2e5 + 4;
int n, q;
int a[NS], lv[NS], rv[NS];
int lmx[NS][20], rmn[NS][20];

unordered_map<int, int> dp[NS][2];

int sol(int l, int r, int dir){
    if(l == 1 && r == n) return 0;
    if(dp[l][dir][r]) return dp[l][dir][r];

    int ans = 0;
    if(!dir){
        int nl = l;
        for(int i = 19; i >= 0; --i){
            if(nl - (1 << i) >= 1 && lmx[nl][i] <= a[r + 1]){
                nl -= (1 << i);
            }
        }
        ans += a[l] - a[nl];
        if(l == nl){
            ans += a[r + 1] - a[nl] + sol(nl, r + 1, 1);
        }
        else{
            ans += sol(nl, r, 0);
        }
    }
    else{
        int nr = r;
        for(int i = 19; i >= 0; --i){
            if(nr + (1 << i) <= n && rmn[nr][i] > a[l - 1]){
                nr += (1 << i);
            }
        }
        ans += a[nr] - a[r];
        if(r == nr){
            ans += a[nr] - a[l - 1] + sol(l - 1, nr, 0);
        }
        else{
            ans += sol(l, nr, 1);
        }
    }

    return (dp[l][dir][r] = ans);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    a[0] = -(int)1e18, a[n + 1] = (int)1e18;
    for(int i = 1; i <= n; ++i){
        lv[i] = a[i] * 2 - a[i - 1];
        rv[i] = 2 * a[i] - a[i + 1];

        lmx[i][0] = lv[i];
        rmn[i][0] = rv[i];
    }
    for(int j = 1; j < 20; ++j){
        for(int i = 1; i <= n; ++i){
            lmx[i][j] = lmx[i][j - 1];
            if(i - (1 << (j - 1)) >= 1){
                lmx[i][j] = max(lmx[i][j], lmx[i - (1 << (j - 1))][j - 1]);
            }
            rmn[i][j] = rmn[i][j - 1];
            if(i + (1 << (j - 1)) <= n){
                rmn[i][j] = min(rmn[i][j], rmn[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    cin >> q;
    while(q--){
        int x;
        cin >> x;

        int p = lower_bound(a + 1, a + n + 1, x) - a;

        if(p == n + 1 || (p > 1 && x - a[p - 1] <= a[p] - x)){
            --p;
        }

        cout << sol(p, p, 0) + abs(a[p] - x) << '\n';
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	22228 KB	Output is correct
2	Correct	12 ms	22956 KB	Output is correct
3	Correct	13 ms	22844 KB	Output is correct
4	Correct	13 ms	22868 KB	Output is correct
5	Correct	12 ms	22868 KB	Output is correct
6	Correct	13 ms	22884 KB	Output is correct
7	Correct	14 ms	22868 KB	Output is correct
8	Correct	12 ms	22228 KB	Output is correct
9	Correct	12 ms	22228 KB	Output is correct
10	Correct	12 ms	22228 KB	Output is correct
11	Correct	12 ms	22220 KB	Output is correct
12	Correct	13 ms	22188 KB	Output is correct
13	Correct	13 ms	22176 KB	Output is correct
14	Correct	13 ms	22868 KB	Output is correct
15	Correct	12 ms	22868 KB	Output is correct
16	Correct	12 ms	22868 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	22228 KB	Output is correct
2	Correct	12 ms	22956 KB	Output is correct
3	Correct	13 ms	22844 KB	Output is correct
4	Correct	13 ms	22868 KB	Output is correct
5	Correct	12 ms	22868 KB	Output is correct
6	Correct	13 ms	22884 KB	Output is correct
7	Correct	14 ms	22868 KB	Output is correct
8	Correct	12 ms	22228 KB	Output is correct
9	Correct	12 ms	22228 KB	Output is correct
10	Correct	12 ms	22228 KB	Output is correct
11	Correct	12 ms	22220 KB	Output is correct
12	Correct	13 ms	22188 KB	Output is correct
13	Correct	13 ms	22176 KB	Output is correct
14	Correct	13 ms	22868 KB	Output is correct
15	Correct	12 ms	22868 KB	Output is correct
16	Correct	12 ms	22868 KB	Output is correct
17	Correct	108 ms	89492 KB	Output is correct
18	Correct	110 ms	89420 KB	Output is correct
19	Correct	119 ms	89580 KB	Output is correct
20	Correct	110 ms	89432 KB	Output is correct
21	Correct	110 ms	89452 KB	Output is correct
22	Correct	117 ms	89532 KB	Output is correct
23	Correct	111 ms	89480 KB	Output is correct
24	Correct	113 ms	89548 KB	Output is correct
25	Correct	111 ms	89536 KB	Output is correct
26	Correct	117 ms	89536 KB	Output is correct
27	Correct	114 ms	89540 KB	Output is correct
28	Correct	113 ms	89544 KB	Output is correct
29	Correct	128 ms	89536 KB	Output is correct
30	Correct	114 ms	89544 KB	Output is correct
31	Correct	115 ms	89540 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	22228 KB	Output is correct
2	Correct	12 ms	22240 KB	Output is correct
3	Correct	11 ms	22212 KB	Output is correct
4	Correct	11 ms	22148 KB	Output is correct
5	Correct	11 ms	22228 KB	Output is correct
6	Correct	11 ms	22240 KB	Output is correct
7	Correct	430 ms	116596 KB	Output is correct
8	Correct	412 ms	116568 KB	Output is correct
9	Correct	419 ms	116644 KB	Output is correct
10	Correct	438 ms	116624 KB	Output is correct
11	Correct	417 ms	116648 KB	Output is correct
12	Correct	424 ms	116696 KB	Output is correct
13	Correct	48 ms	24216 KB	Output is correct
14	Correct	37 ms	22760 KB	Output is correct
15	Correct	356 ms	116180 KB	Output is correct
16	Correct	343 ms	116044 KB	Output is correct
17	Correct	358 ms	116024 KB	Output is correct
18	Correct	47 ms	24068 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	22228 KB	Output is correct
2	Correct	12 ms	22956 KB	Output is correct
3	Correct	13 ms	22844 KB	Output is correct
4	Correct	13 ms	22868 KB	Output is correct
5	Correct	12 ms	22868 KB	Output is correct
6	Correct	13 ms	22884 KB	Output is correct
7	Correct	14 ms	22868 KB	Output is correct
8	Correct	12 ms	22228 KB	Output is correct
9	Correct	12 ms	22228 KB	Output is correct
10	Correct	12 ms	22228 KB	Output is correct
11	Correct	12 ms	22220 KB	Output is correct
12	Correct	13 ms	22188 KB	Output is correct
13	Correct	13 ms	22176 KB	Output is correct
14	Correct	13 ms	22868 KB	Output is correct
15	Correct	12 ms	22868 KB	Output is correct
16	Correct	12 ms	22868 KB	Output is correct
17	Correct	108 ms	89492 KB	Output is correct
18	Correct	110 ms	89420 KB	Output is correct
19	Correct	119 ms	89580 KB	Output is correct
20	Correct	110 ms	89432 KB	Output is correct
21	Correct	110 ms	89452 KB	Output is correct
22	Correct	117 ms	89532 KB	Output is correct
23	Correct	111 ms	89480 KB	Output is correct
24	Correct	113 ms	89548 KB	Output is correct
25	Correct	111 ms	89536 KB	Output is correct
26	Correct	117 ms	89536 KB	Output is correct
27	Correct	114 ms	89540 KB	Output is correct
28	Correct	113 ms	89544 KB	Output is correct
29	Correct	128 ms	89536 KB	Output is correct
30	Correct	114 ms	89544 KB	Output is correct
31	Correct	115 ms	89540 KB	Output is correct
32	Correct	12 ms	22228 KB	Output is correct
33	Correct	12 ms	22240 KB	Output is correct
34	Correct	11 ms	22212 KB	Output is correct
35	Correct	11 ms	22148 KB	Output is correct
36	Correct	11 ms	22228 KB	Output is correct
37	Correct	11 ms	22240 KB	Output is correct
38	Correct	430 ms	116596 KB	Output is correct
39	Correct	412 ms	116568 KB	Output is correct
40	Correct	419 ms	116644 KB	Output is correct
41	Correct	438 ms	116624 KB	Output is correct
42	Correct	417 ms	116648 KB	Output is correct
43	Correct	424 ms	116696 KB	Output is correct
44	Correct	48 ms	24216 KB	Output is correct
45	Correct	37 ms	22760 KB	Output is correct
46	Correct	356 ms	116180 KB	Output is correct
47	Correct	343 ms	116044 KB	Output is correct
48	Correct	358 ms	116024 KB	Output is correct
49	Correct	47 ms	24068 KB	Output is correct
50	Correct	452 ms	121128 KB	Output is correct
51	Correct	455 ms	121188 KB	Output is correct
52	Correct	464 ms	120856 KB	Output is correct
53	Correct	494 ms	126772 KB	Output is correct
54	Correct	491 ms	126640 KB	Output is correct
55	Correct	485 ms	126424 KB	Output is correct
56	Correct	163 ms	92024 KB	Output is correct
57	Correct	164 ms	92036 KB	Output is correct
58	Correct	161 ms	91980 KB	Output is correct

답안 #796022

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 30.0 / 30.0

Subtask #4 55.0 / 55.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
30.0 / 30.0

Subtask #4
55.0 / 55.0