Submission #1210158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210158		dima2101	Bitaro's travel (JOI23_travel)	C++20	100 / 100	267 ms	8800 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);
    std::vector<std::pair<int, int>> now;
    now.push_back({1e13, 0});
    for (int i = 0; i < n; i++)
    {
        if (i == n - 1)
        {
            prev[i] = 0;
            continue;
        }
        if (i != 0)
        {
            int tmp = 2 * x[i] - x[i - 1];
            while (now.size() > 0 && now.back().first <= tmp)
            {
                now.pop_back();
            }
            now.push_back({tmp, i});
        }
        int l = 0, r = now.size();
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (x[i + 1] < now[mid].first)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        // std::cout << i << ' ' << prev[i] << std::endl;
        // for (auto j : now)
        // {
        //     std::cout << j.first << ' ' << j.second << std::endl;
        // }
        prev[i] = now[l].second;
    }

    std::vector<int> next(n);
    now.clear();
    now.push_back({-1e13, n - 1});
    for (int i = n - 1; i >= 0; i--)
    {
        if (i == 0)
        {
            next[i] = n - 1;
            continue;
        }

        if (i != n - 1)
        {
            int tmp = 2 * x[i] - x[i + 1];
            while (now.size() > 0 && now.back().first >= tmp)
            {
                now.pop_back();
            }
            now.push_back({tmp, i});
        }

        int l = 0, r = now.size();
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (now[mid].first <= x[i - 1])
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        //  std::cout << i << ' ' << next[i] << ' ' << last << std::endl;
        next[i] = now[l].second;
    }
    // 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: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55