Submission #1245639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245639		Zbyszek99	Bitaro's travel (JOI23_travel)	C++20	100 / 100	412 ms	47240 KiB

travel

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct stable
{
    int min_[200002][18];
    void init(vi arr)
    {
        rep(i,siz(arr)) min_[i][0] = arr[i];
        rep2(bit,1,17)
        {
            rep(i,siz(arr))
            {
                min_[i][bit] = min(min_[i][bit-1],(i+(1 << bit)/2 < siz(arr) ? min_[i+(1 << bit)/2][bit-1] : (int)1e9));
            }
        }
    }
    int query(int l, int r)
    {
        int lg = __lg(r-l+1);
        return min(min_[l][lg],min_[r-(1<<lg)+1][lg]);
    }
};

stable left_table;
stable right_table;
ll X[200005];
int n;

ll rek(int l, int r, int poz)
{
    if(l == 1 && r == n) return 0;
    if(l == 1) return X[n] - X[poz];
    if(r == n) return X[poz] - X[1];
    if(X[poz] - X[l-1] <= X[r+1] - X[poz])
    {
        int l2 = 1;
        int r2 = l-1;
        int ans = 0;
        while(l2 <= r2)
        {
            int mid = (l2+r2)/2;
            if(-right_table.query(mid+1,l) <= r)
            {
                ans = mid;
                r2 = mid-1;
            }
            else
            {
                l2 = mid+1;
            }
        }
        return X[poz] - X[ans] + rek(ans,r,ans);
    }
    else
    {
        int l2 = r+1;
        int r2 = n;
        int ans = 0;
        while(l2 <= r2)
        {
            int mid = (l2+r2)/2;
            if(left_table.query(r,mid-1) >= l)
            {
                ans = mid;
                l2 = mid+1;
            }
            else
            {
                r2 = mid-1;
            }
        }
        return X[ans]-X[poz] + rek(l,ans,ans);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    cin >> n;
    X[0] = -3e9;
    X[n+1] = 3e9; 
    set<pll> X_set;
    rep2(i,1,n)
    {
        cin >> X[i];
        X_set.insert({X[i],i});
    }
    vi left_bor(n+2,0);
    vi right_bor(n+2,0);
    rep2(i,1,n)
    {
        int l = 1;
        int r = i;
        int ans_left = i;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(abs(X[i]-X[mid]) <= abs(X[i]-X[i+1]))
            {
                ans_left = mid;
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }
        l = i;
        r = n;
        int ans_right = i;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(abs(X[i]-X[mid]) < abs(X[i]-X[i-1]))
            {
                ans_right = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        left_bor[i] = ans_left;
        right_bor[i] = -ans_right;
    }
    left_table.init(left_bor);
    right_table.init(right_bor);
    int q;
    cin >> q;
    rep(qq,q)
    {
        ll s;
        cin >> s;
        auto nxt = X_set.lower_bound({s,-1});
        pll d = {1e18,-1};
        if(nxt != X_set.end()) d = min(d,{abs(s-(*nxt).ff),(*nxt).ss});
        if(nxt != X_set.begin())
        {
            nxt--;
            d = min(d,{abs(s-(*nxt).ff),(*nxt).ss});
        }
        cout << d.ff + rek(d.ss,d.ss,d.ss) << "\n";
    }
}

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