Submission #874249

#	Time	Username	Problem	Language	Result	Execution time	Memory
874249		prvocislo	Bitaro's travel (JOI23_travel)	C++17	100 / 100	100 ms	9732 KiB

travel

#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int n;
vector<ll> d;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    d.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> d[i];
    vector<int> li(n, -1), ri(n, -1);
    set<pair<ll, int> > id;
    for (int i = n - 2; i >= 0; i--)
    {
        auto it = id.upper_bound({ d[i], n });
        ri[i + 1] = (it == id.begin() ? n - 1 : prev(it)->second);
        pair<ll, int> nw = { 2 * d[i] - d[i + 1], i };
        while (!id.empty() && id.rbegin()->first >= nw.first) id.erase(*id.rbegin());
        id.insert(nw);
    }
    ri[0] = n - 1;
    id.clear();
    for (int i = 0; i + 1 < n; i++)
    {
        auto it = id.upper_bound({ d[i + 1], n });
        li[i] = (it == id.end() ? 0 : it->second);
        pair<ll, int> nw = { 2 * d[i + 1] - d[i], i + 1 };
        while (!id.empty() && id.begin()->first <= nw.first) id.erase(*id.begin());
        id.insert(nw);
    }
    li[n - 1] = 0;
    int q;
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        int i = lower_bound(d.begin(), d.end(), x) - d.begin();
        if (i == n || (i && x - d[i - 1] <= d[i] - x)) i--;
        ll ans = abs(d[i] - x);
        while (i && i != n - 1)
        {
            if (i != ri[i]) ans += d[ri[i]] - d[i], i = ri[i];
            else            ans += d[i] - d[li[i]], i = li[i];
        }
        ans += d[n - 1] - d[0];
        //cout << "                       ";
        cout << ans << "\n";
    }
    return 0;
}

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