Submission #1252074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252074		hainam2k9	Bitaro's travel (JOI23_travel)	C++20	100 / 100	174 ms	29640 KiB

travel

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,q,a[MAXN],stL[20][MAXN],stR[20][MAXN];
void build(){
    for(int i = 1; i<=n; ++i)
        stL[0][i]=2*a[i]-a[i-1],
        stR[0][i]=2*a[i]-a[i+1];
    stL[0][1]=2e9;
    for(int i = 1; i<=__lg(n); ++i)
        for(int j = 1<<i; j<=n; ++j)
            stL[i][j]=max(stL[i-1][j],stL[i-1][j-(1<<(i-1))]);
    stR[0][n]=-2e9;
    for(int i = 1; i<=__lg(n); ++i)
        for(int j = 1; j+(1<<i)-1<=n; ++j)
            stR[i][j]=min(stR[i-1][j],stR[i-1][j+(1<<(i-1))]);
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n;
    for(int i = 1; i<=n; ++i)
        cin >> a[i];
    build();
    cin >> q;
    while(q--){
        int x;
        ll rs=0;
        cin >> x;
        if(x<=a[1]) rs=a[1]-x, x=1;
        else if(x>=a[n]) rs=x-a[n], x=n;
        else{
            int pos=ub(a+1,a+n+1,x)-a;
            if(x-a[pos-1]<=a[pos]-x) rs+=x-a[pos-1], x=pos-1;
            else rs+=a[pos]-x, x=pos;
        }
        int curL=x, curR=x;
        while(curL>1||curR<n){
            if(curL==1) rs+=a[n]-a[x], curR=n;
            else if(curR==n) rs+=a[x]-a[1], curL=1;
            else{
                if(a[x]-a[curL-1]<=a[curR+1]-a[x]){
                    int MAX=0,pos=curL-1;
                    for(int i = __lg(n); i>=0; --i)
                        if(pos>1<<i&&max(MAX,stL[i][pos])<=a[curR+1])
                            MAX=max(MAX,stL[i][pos]), pos-=1<<i;
                    curL=pos, rs+=a[x]-a[curL], x=curL;
                }else{
                    int MIN=1e9, pos=curR+1;
                    for(int i = __lg(n); i>=0; --i)
                        if(pos+(1<<i)<=n&&min(MIN,stR[i][pos])>a[curL-1])
                            MIN=min(MIN,stR[i][pos]), pos+=1<<i;
                    curR=pos, rs+=a[curR]-a[x], x=curR;
                }
            }
        }
        cout << rs << "\n";
    }
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:39:45: note: in expansion of macro 'fo'
   39 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
travel.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:39:45: note: in expansion of macro 'fo'
   39 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

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