답안 #1002227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002227	2024-06-19T11:07:38 Z	LonlyR	Bitaro's travel (JOI23_travel)	C++17	100 / 100	137 ms	68432 KB

travel

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int le[19][maxn], ri[19][maxn], a[maxn], ans[maxn];

int solve(int x)
{
    if (ans[x] != -1) return ans[x];
    int l = x, r = x, pos = a[x], res = 0;
    while (l != 1 || r != n)
    {
        for (int i = 18; i >= 0; i--)
            if (l - (1 << i) >= 1 && le[i][l] <= a[r + 1])
                l -= 1 << i, res += pos - a[l], pos = a[l];
        for (int i = 18; i >= 0; i--)
            if (r + (1 << i) <= n && ri[i][r] < -a[l - 1])
                r += 1 << i, res += a[r] - pos, pos = a[r];
    }
    return ans[x] = res;
}

int qry(int s)
{
	int r = lower_bound(a + 1, a + n + 1, s) - a, l = r - 1;
	if(s - a[l] <= a[r] - s) return s - a[l] + solve(l);
	else return a[r] - s + solve(r);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n;
    a[0] = -1e12; a[n + 1] = 1e12;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        le[0][i] = a[i] * 2 - a[i - 1], ri[0][i] = a[i + 1] - a[i] * 2;
    for (int j = 1; j < 19; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            ri[j][i] = max(ri[j - 1][i], ri[j - 1][i + (1 << (j - 1))]);
    for (int j = 1; j < 19; j++)
        for (int i = n; i - (1 << j) + 1 >= 1; i--)
            le[j][i] = max(le[j - 1][i], le[j - 1][i - (1 << (j - 1))]);
    memset(ans, -1, sizeof ans);
    cin >> m;
    for (int i = 1, x; i <= m; i++)
        cin >> x, cout << qry(x) << "\n";
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12892 KB	Output is correct
2	Correct	4 ms	39656 KB	Output is correct
3	Correct	4 ms	39516 KB	Output is correct
4	Correct	4 ms	39512 KB	Output is correct
5	Correct	4 ms	39516 KB	Output is correct
6	Correct	5 ms	39516 KB	Output is correct
7	Correct	4 ms	39512 KB	Output is correct
8	Correct	1 ms	6744 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	1 ms	6748 KB	Output is correct
11	Correct	1 ms	6628 KB	Output is correct
12	Correct	2 ms	10700 KB	Output is correct
13	Correct	3 ms	16988 KB	Output is correct
14	Correct	4 ms	39512 KB	Output is correct
15	Correct	5 ms	39516 KB	Output is correct
16	Correct	5 ms	39516 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12892 KB	Output is correct
2	Correct	4 ms	39656 KB	Output is correct
3	Correct	4 ms	39516 KB	Output is correct
4	Correct	4 ms	39512 KB	Output is correct
5	Correct	4 ms	39516 KB	Output is correct
6	Correct	5 ms	39516 KB	Output is correct
7	Correct	4 ms	39512 KB	Output is correct
8	Correct	1 ms	6744 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	1 ms	6748 KB	Output is correct
11	Correct	1 ms	6628 KB	Output is correct
12	Correct	2 ms	10700 KB	Output is correct
13	Correct	3 ms	16988 KB	Output is correct
14	Correct	4 ms	39512 KB	Output is correct
15	Correct	5 ms	39516 KB	Output is correct
16	Correct	5 ms	39516 KB	Output is correct
17	Correct	33 ms	64084 KB	Output is correct
18	Correct	27 ms	61268 KB	Output is correct
19	Correct	24 ms	63936 KB	Output is correct
20	Correct	30 ms	61240 KB	Output is correct
21	Correct	42 ms	61332 KB	Output is correct
22	Correct	24 ms	63892 KB	Output is correct
23	Correct	29 ms	61400 KB	Output is correct
24	Correct	27 ms	61304 KB	Output is correct
25	Correct	20 ms	63908 KB	Output is correct
26	Correct	27 ms	61324 KB	Output is correct
27	Correct	30 ms	61264 KB	Output is correct
28	Correct	23 ms	64076 KB	Output is correct
29	Correct	29 ms	61568 KB	Output is correct
30	Correct	27 ms	61264 KB	Output is correct
31	Correct	27 ms	61268 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	12892 KB	Output is correct
2	Correct	2 ms	16988 KB	Output is correct
3	Correct	1 ms	6748 KB	Output is correct
4	Correct	1 ms	6748 KB	Output is correct
5	Correct	1 ms	6748 KB	Output is correct
6	Correct	1 ms	6748 KB	Output is correct
7	Correct	100 ms	66132 KB	Output is correct
8	Correct	84 ms	66132 KB	Output is correct
9	Correct	86 ms	65888 KB	Output is correct
10	Correct	85 ms	66120 KB	Output is correct
11	Correct	83 ms	65892 KB	Output is correct
12	Correct	84 ms	66056 KB	Output is correct
13	Correct	27 ms	10588 KB	Output is correct
14	Correct	25 ms	7772 KB	Output is correct
15	Correct	89 ms	67156 KB	Output is correct
16	Correct	89 ms	67124 KB	Output is correct
17	Correct	81 ms	67152 KB	Output is correct
18	Correct	27 ms	10428 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12892 KB	Output is correct
2	Correct	4 ms	39656 KB	Output is correct
3	Correct	4 ms	39516 KB	Output is correct
4	Correct	4 ms	39512 KB	Output is correct
5	Correct	4 ms	39516 KB	Output is correct
6	Correct	5 ms	39516 KB	Output is correct
7	Correct	4 ms	39512 KB	Output is correct
8	Correct	1 ms	6744 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	1 ms	6748 KB	Output is correct
11	Correct	1 ms	6628 KB	Output is correct
12	Correct	2 ms	10700 KB	Output is correct
13	Correct	3 ms	16988 KB	Output is correct
14	Correct	4 ms	39512 KB	Output is correct
15	Correct	5 ms	39516 KB	Output is correct
16	Correct	5 ms	39516 KB	Output is correct
17	Correct	33 ms	64084 KB	Output is correct
18	Correct	27 ms	61268 KB	Output is correct
19	Correct	24 ms	63936 KB	Output is correct
20	Correct	30 ms	61240 KB	Output is correct
21	Correct	42 ms	61332 KB	Output is correct
22	Correct	24 ms	63892 KB	Output is correct
23	Correct	29 ms	61400 KB	Output is correct
24	Correct	27 ms	61304 KB	Output is correct
25	Correct	20 ms	63908 KB	Output is correct
26	Correct	27 ms	61324 KB	Output is correct
27	Correct	30 ms	61264 KB	Output is correct
28	Correct	23 ms	64076 KB	Output is correct
29	Correct	29 ms	61568 KB	Output is correct
30	Correct	27 ms	61264 KB	Output is correct
31	Correct	27 ms	61268 KB	Output is correct
32	Correct	1 ms	12892 KB	Output is correct
33	Correct	2 ms	16988 KB	Output is correct
34	Correct	1 ms	6748 KB	Output is correct
35	Correct	1 ms	6748 KB	Output is correct
36	Correct	1 ms	6748 KB	Output is correct
37	Correct	1 ms	6748 KB	Output is correct
38	Correct	100 ms	66132 KB	Output is correct
39	Correct	84 ms	66132 KB	Output is correct
40	Correct	86 ms	65888 KB	Output is correct
41	Correct	85 ms	66120 KB	Output is correct
42	Correct	83 ms	65892 KB	Output is correct
43	Correct	84 ms	66056 KB	Output is correct
44	Correct	27 ms	10588 KB	Output is correct
45	Correct	25 ms	7772 KB	Output is correct
46	Correct	89 ms	67156 KB	Output is correct
47	Correct	89 ms	67124 KB	Output is correct
48	Correct	81 ms	67152 KB	Output is correct
49	Correct	27 ms	10428 KB	Output is correct
50	Correct	134 ms	68180 KB	Output is correct
51	Correct	133 ms	68180 KB	Output is correct
52	Correct	137 ms	68132 KB	Output is correct
53	Correct	113 ms	68432 KB	Output is correct
54	Correct	112 ms	68072 KB	Output is correct
55	Correct	116 ms	68176 KB	Output is correct
56	Correct	50 ms	67924 KB	Output is correct
57	Correct	56 ms	67892 KB	Output is correct
58	Correct	57 ms	68108 KB	Output is correct

답안 #1002227

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