oj.uz

Submission #895198

# Submission time Handle Problem Language Result Execution time Memory
895198 2023-12-29T15:13:26 Z boris_mihov Bitaro's travel (JOI23_travel) C++17
100 / 100
 175 ms 69968 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXLOG = 20 + 5;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n, q;
int getLog[MAXN];
struct SparseMAX
{
    llong sparse[MAXLOG][MAXN];
    void build(llong s[])
    {
        for (int i = 1 ; i < n ; ++i)
        {
            sparse[0][i] = s[i];
        }

        for (int log = 1 ; (1 << log) < n ; ++log)
        {
            for (int i = 1 ; i + (1 << log) - 1 < n ; ++i)
            {
                sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
            }
        }

        for (int i = 1 ; i < n ; ++i)
        {
            getLog[i] = getLog[i - 1];
            if ((1 << getLog[i] + 1) < i) getLog[i]++;
        }
    }

    inline int findMAX(int l, int r)
    {
        int log = getLog[r - l + 1];
        return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
    }
};

struct SparseMIN
{
    llong sparse[MAXLOG][MAXN];
    void build(llong s[])
    {
        for (int i = 1 ; i < n ; ++i)
        {
            sparse[0][i] = s[i];
        }

        for (int log = 1 ; (1 << log) < n ; ++log)
        {
            for (int i = 1 ; i + (1 << log) - 1 < n ; ++i)
            {
                sparse[log][i] = std::min(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
            }
        }

        for (int i = 1 ; i < n ; ++i)
        {
            getLog[i] = getLog[i - 1];
            if ((1 << getLog[i] + 1) < i) getLog[i]++;
        }
    }

    inline int findMIN(int l, int r)
    {
        int log = getLog[r - l + 1];
        return std::min(sparse[log][l], sparse[log][r - (1 << log) + 1]);
    }
};

llong s[MAXN];
llong a[MAXN];
SparseMAX left;
SparseMIN right;
llong precalc[MAXN];

void solve()
{
    for (int i = 1 ; i < n ; ++i)
    {
        s[i] = 2 * a[i + 1] - a[i];
    }

    left.build(s);
    for (int i = 1 ; i < n ; ++i)
    {
        s[i] = 2 * a[i] - a[i + 1];
    }

    right.build(s);
    a[0] = -1e18;
    a[n + 1] = 1e18;

    for (int i = 1 ; i <= n ; ++i)
    {
        int l = i - 1;
        int r = i + 1;
        bool dir = false;
        if (a[i] - a[i - 1] <= a[i + 1] - a[i])
        {
            dir = true;
        }

        precalc[i] += std::min(a[i] - a[i - 1], a[i + 1] - a[i]);
        if (n == 1) precalc[i] = 0;
        while (l >= 1 || r <= n)
        {
            if (dir)
            {
                int ll = 0, rr = l, mid;
                while (ll < rr - 1)
                {
                    mid = (ll + rr) / 2;
                    if (left.findMAX(mid, l - 1) > a[r]) ll = mid;
                    else rr = mid;
                }
                
                precalc[i] += a[l] - a[rr];
                if (r <= n) precalc[i] += a[r] - a[rr]; l = ll;
                dir = false; 
            } else
            {
                int ll = r - 1, rr = n, mid;
                while (ll < rr - 1)
                {
                    mid = (ll + rr) / 2;
                    if (right.findMIN(r, mid) > a[l]) ll = mid;
                    else rr = mid;
                }

                precalc[i] += a[rr] - a[r];
                if (l >= 1) precalc[i] += a[rr] - a[l]; r = rr + 1;
                dir = true; 
            }
        }
    }

    llong pos;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> pos;
        int l = 0, r = n + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (a[mid] < pos) l = mid;
            else r = mid;
        }

        if (pos - a[l] <= a[r] - pos)
        {
            std::cout << precalc[l] + pos - a[l] << '\n';
        } else
        {
            std::cout << precalc[r] + a[r] - pos << '\n';
        }
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    std::cin >> q;
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    input();
    solve();

    return 0;
}

Compilation message

travel.cpp: In member function 'void SparseMAX::build(llong*)':
travel.cpp:28:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |                 sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                         ~~~~^~~
travel.cpp:35:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   35 |             if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                       ~~~~~~~~~~^~~
travel.cpp: In member function 'void SparseMIN::build(llong*)':
travel.cpp:60:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   60 |                 sparse[log][i] = std::min(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                         ~~~~^~~
travel.cpp:67:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   67 |             if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                       ~~~~~~~~~~^~~
travel.cpp: In function 'void solve()':
travel.cpp:126:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  126 |                 if (r <= n) precalc[i] += a[r] - a[rr]; l = ll;
      |                 ^~
travel.cpp:126:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  126 |                 if (r <= n) precalc[i] += a[r] - a[rr]; l = ll;
      |                                                         ^
travel.cpp:139:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  139 |                 if (l >= 1) precalc[i] += a[rr] - a[l]; r = rr + 1;
      |                 ^~
travel.cpp:139:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  139 |                 if (l >= 1) precalc[i] += a[rr] - a[l]; r = rr + 1;
      |                                                         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 11 ms 41308 KB Output is correct
3 Correct 5 ms 41752 KB Output is correct
4 Correct 5 ms 41488 KB Output is correct
5 Correct 5 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 41476 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 5 ms 41304 KB Output is correct
15 Correct 5 ms 41520 KB Output is correct
16 Correct 5 ms 41308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 11 ms 41308 KB Output is correct
3 Correct 5 ms 41752 KB Output is correct
4 Correct 5 ms 41488 KB Output is correct
5 Correct 5 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 41476 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 5 ms 41304 KB Output is correct
15 Correct 5 ms 41520 KB Output is correct
16 Correct 5 ms 41308 KB Output is correct
17 Correct 95 ms 65632 KB Output is correct
18 Correct 99 ms 65680 KB Output is correct
19 Correct 90 ms 65372 KB Output is correct
20 Correct 91 ms 65364 KB Output is correct
21 Correct 90 ms 65620 KB Output is correct
22 Correct 92 ms 65528 KB Output is correct
23 Correct 89 ms 65620 KB Output is correct
24 Correct 71 ms 65612 KB Output is correct
25 Correct 69 ms 65612 KB Output is correct
26 Correct 72 ms 65616 KB Output is correct
27 Correct 71 ms 65616 KB Output is correct
28 Correct 68 ms 65364 KB Output is correct
29 Correct 132 ms 65360 KB Output is correct
30 Correct 134 ms 65560 KB Output is correct
31 Correct 130 ms 65432 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 92 ms 67396 KB Output is correct
8 Correct 93 ms 67408 KB Output is correct
9 Correct 98 ms 67384 KB Output is correct
10 Correct 98 ms 67412 KB Output is correct
11 Correct 95 ms 67580 KB Output is correct
12 Correct 94 ms 67408 KB Output is correct
13 Correct 31 ms 6344 KB Output is correct
14 Correct 22 ms 3676 KB Output is correct
15 Correct 109 ms 68608 KB Output is correct
16 Correct 124 ms 68596 KB Output is correct
17 Correct 113 ms 68556 KB Output is correct
18 Correct 38 ms 6152 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 11 ms 41308 KB Output is correct
3 Correct 5 ms 41752 KB Output is correct
4 Correct 5 ms 41488 KB Output is correct
5 Correct 5 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 41476 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 5 ms 41304 KB Output is correct
15 Correct 5 ms 41520 KB Output is correct
16 Correct 5 ms 41308 KB Output is correct
17 Correct 95 ms 65632 KB Output is correct
18 Correct 99 ms 65680 KB Output is correct
19 Correct 90 ms 65372 KB Output is correct
20 Correct 91 ms 65364 KB Output is correct
21 Correct 90 ms 65620 KB Output is correct
22 Correct 92 ms 65528 KB Output is correct
23 Correct 89 ms 65620 KB Output is correct
24 Correct 71 ms 65612 KB Output is correct
25 Correct 69 ms 65612 KB Output is correct
26 Correct 72 ms 65616 KB Output is correct
27 Correct 71 ms 65616 KB Output is correct
28 Correct 68 ms 65364 KB Output is correct
29 Correct 132 ms 65360 KB Output is correct
30 Correct 134 ms 65560 KB Output is correct
31 Correct 130 ms 65432 KB Output is correct
32 Correct 2 ms 16732 KB Output is correct
33 Correct 3 ms 18780 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 0 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 1 ms 2392 KB Output is correct
38 Correct 92 ms 67396 KB Output is correct
39 Correct 93 ms 67408 KB Output is correct
40 Correct 98 ms 67384 KB Output is correct
41 Correct 98 ms 67412 KB Output is correct
42 Correct 95 ms 67580 KB Output is correct
43 Correct 94 ms 67408 KB Output is correct
44 Correct 31 ms 6344 KB Output is correct
45 Correct 22 ms 3676 KB Output is correct
46 Correct 109 ms 68608 KB Output is correct
47 Correct 124 ms 68596 KB Output is correct
48 Correct 113 ms 68556 KB Output is correct
49 Correct 38 ms 6152 KB Output is correct
50 Correct 152 ms 69968 KB Output is correct
51 Correct 174 ms 69576 KB Output is correct
52 Correct 144 ms 69752 KB Output is correct
53 Correct 128 ms 69580 KB Output is correct
54 Correct 142 ms 69716 KB Output is correct
55 Correct 128 ms 69680 KB Output is correct
56 Correct 167 ms 69456 KB Output is correct
57 Correct 166 ms 69580 KB Output is correct
58 Correct 175 ms 69552 KB Output is correct