Submission #895198

#	Time	Username	Problem	Language	Result	Execution time	Memory
895198		boris_mihov	Bitaro's travel (JOI23_travel)	C++17	100 / 100	175 ms	69968 KiB

travel

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55