Submission #1210154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210154		dima2101	Bitaro's travel (JOI23_travel)	C++20	5 / 100	3097 ms	6680 KiB

travel

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

signed main()
{
    int n;
    std::cin >> n;

    std::vector<int> x(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> x[i];
    }

    std::vector<int> prev(n);
    for (int i = 0; i < n; i++)
    {
        if (i == n - 1)
        {
            prev[i] = 0;
            continue;
        }
        int last = 0;
        for (int j = i; j >= 1; j--)
        {
            if (x[i + 1] - x[j] < x[j] - x[j - 1])
            {
                last = j;
                break;
            }
        }
        // std::cout << i << ' ' << last << std::endl;
        prev[i] = last;
    }

    std::vector<int> next(n);
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            next[i] = n - 1;
            continue;
        }
        int last = n - 1;
        for (int j = i; j < n - 1; j++)
        {
            if (x[j] - x[i - 1] <= x[j + 1] - x[j])
            {
                last = j;
                break;
            }
        }
        //  std::cout << i << ' ' << next[i] << ' ' << last << std::endl;
        next[i] = last;
    }
    // exit(0);

    std::vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        int l = i, r = i;
        int j = i;
        while ((r - l + 1) != n)
        {
            //'std::cout << l << ' ' << r << ' ' << j << ' ' << next[j] << ' ' << prev[j] << std::endl;
            if (next[j] != j)
            {
                r = next[j];
                ans[i] += x[r] - x[j];
                j = r;
            }
            else
            {

                l = prev[j];

                ans[i] += x[j] - x[l];
                j = l;
            }
        }
    }

    int q;
    std::cin >> q;

    for (int i = 0; i < q; i++)
    {
        int now;
        std::cin >> now;

        // if (n == 1)
        // {
        //     std::cout << std::abs(x[0] - now) << std::endl;
        //     ;
        //     continue;
        // }

        int l = 0, r = x.size();
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (x[mid] <= now)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        int cur = 0;
        int now_ind = -1;
        if (r == x.size())
        {
            cur += std::abs(now - x.back());
            now_ind = l;
        }
        else
        {
            if (std::abs(x[l] - now) <= std::abs(x[r] - now))
            {
                now_ind = l;
                cur += std::abs(x[l] - now);
            }
            else
            {
                now_ind = r;
                cur += std::abs(x[r] - now);
            }
        }
        std::cout << ans[now_ind] + cur << std::endl;
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 55