제출 #1103848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103848		vjudge1	Bitaro's travel (JOI23_travel)	C++17	100 / 100	145 ms	112312 KiB

travel

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair

#ifdef NCGM
#include<C:/NCGM/headers/debug.h>
#else
#define debug(...) "fr";
#endif

using namespace std;


const int N=1e6+13;

int n;
ll a[N],b[N],st[20][N],d[N];

void pre() {
    For(i,1,n) st[0][i]=a[i+1]*2-a[i];
    For(j,1,19)
        for(int i=1;i+(1<<j)-1<=n;i++) st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
}
void pre1() {
    For(i,1,n) st[0][i]=a[i]-a[i-1]*2;
    For(j,1,19)
        for(int i=1;i+(1<<j)-1<=n;i++) st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
}
ll query(int l,int r) {
    int s=__lg(r-l+1);
    return max(st[s][l],st[s][r-(1<<s)+1]);
}
vector<pair<int,ll>> g[N];

void dfs(int u,int p=0) {
    for(auto v: g[u])
    if (v.ff!=p) {
        d[v.ff]=d[u]+v.ss;
        dfs(v.ff,u);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    For(i,1,n) cin >> a[i];
    pre();
    For(i,1,n) b[i]=a[i]-a[i-1];
    For(i,1,n) b[i]+=b[i-1];
    For(i,2,n-1) {
        if (a[i]-a[i-1]<=a[i+1]-a[i]) {
            int l=1,r=i-1;
            while(l<r) {
                int mid=l+(r-l)/2;
                if (query(mid,i-1)<=a[i+1]) r=mid;
                else l=mid+1;
            }
            g[r].pb({i,a[i]-a[r]});
            g[i].pb({r,a[i]-a[r]});
        }
    }
    pre1();
    For(i,2,n-1) {
        if (a[i]-a[i-1]>a[i+1]-a[i])  {
            int l=i+1,r=n;
            while(l<r) {
                int mid=l+(r-l+1)/2;
                if (query(i+1,mid) < -a[i-1]) l=mid;
                else r=mid-1;
            }
            g[l].pb({i,a[l]-a[i]});
            g[i].pb({l,a[l]-a[i]});
        }
    }
    d[1]=d[n]=a[n]-a[1];
    dfs(1);
    dfs(n);
    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        int idx=lower_bound(a+1,a+1+n,x)-a;
        if (idx>1 && idx<=n) {
            if (x-a[idx-1]<=a[idx]-x) cout << x-a[idx-1]+d[idx-1] << endl;
            else cout << a[idx]-x+d[idx] << endl;
        } else if (idx==1) cout << a[idx]-x+d[idx] << endl;
        else cout << x-a[idx-1]+d[idx-1] << endl;
    }


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

travel.cpp: In function 'void pre()':
travel.cpp:37:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   37 |         for(int i=1;i+(1<<j)-1<=n;i++) st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
      |                                                                              ~^~
travel.cpp: In function 'void pre1()':
travel.cpp:42:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |         for(int i=1;i+(1<<j)-1<=n;i++) st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
      |                                                                              ~^~

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