oj.uz

Submission #1002227

# Submission time Handle Problem Language Result Execution time Memory
1002227 2024-06-19T11:07:38 Z LonlyR Bitaro's travel (JOI23_travel) C++17
100 / 100
 137 ms 68432 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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