Submission #1301623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301623		sitingfake	Bitaro's travel (JOI23_travel)	C++20	0 / 100	612 ms	1114112 KiB

travel

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ii pair <int , int>
#define iii pair <int , ii>
#define se second
#define fi first
#define all(v) (v).begin() , (v).end()
#define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
#define bit(x,i) (((x) >> (i)) & 1LL)
#define flip(x,i) ((x) ^ (1LL << (i)))
#define ms(d,x) memset(d , x , sizeof(d))
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right
#define prev __prev
#define next __next
#define sitingfake 1
#define orz 1
//constant

const long long mod = 1e9 + 7;
const long long linf = 4557430888798830399LL;
const long long nlinf = -4485090715960753727LL;
const int LOG = 20;
const int inf = 1061109567;
const int ninf = -1044266559;
const int dx[] = {0 , -1 , 0 , 1};
const int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a < 0) a += mod;
    a %= mod;
    return;
}

void Mul(ll & a, ll b)
{
    (a *= (b % mod)) %= mod;
    return;
}

//code
const int maxn = 2e5 + 7;

int n , q;

int d[maxn] , x[maxn];

int pref[maxn];

int st[4 * maxn][2]; // 0 -> left , 1 -> right

void build(int i , int l , int r)
{
    if(l == r)
    {
        st[i][1] = d[l] - pref[l - 1];
        st[i][0] = d[l] + pref[l];
        return;
    }
    int mid = (r + l) >> 1;
    build(i * 2 , l , mid);
    build(i * 2 + 1 , mid + 1 , r);
    st[i][0] = max(st[i * 2][0] , st[i * 2 + 1][0]);

}

int walk_left(int i , int l , int r , int u , int v , int val)
{
    if(u > r || v < l || st[i][1] + val < 0) return -1;
    if(l == r) return l;
    int mid = (r + l) >> 1;
    int res = walk_left(i * 2 , l , mid , u , v , val);
    if(res == -1) return walk_left(i * 2 + 1 , mid + 1 , r , u , v , val);
    return res;
}

int walk_right(int i , int l , int r , int u , int v , int val)
{
    //cout << l << " " << r << " " << u << " " << v << " " << val << endl;
    if(u > r || v < l || st[i][0] - val <= 0) return -1;
    if(l == r)
    {
        return l;
    }
    int mid = (r + l) >> 1;
    int res = walk_right(i * 2 + 1 , mid + 1 , r , u , v , val);
    if(res == -1)
    {
        return walk_right(i * 2 , l , mid , u , v , val);
    }
    return res;
}

int Query(int u)
{
    if(u == 1 || u == n)
    {
        return pref[n - 1];
    }

    int curLeft = u - 1 , curRight = u;
    int ans = 0;
    // 1 -> right , 0 -> left
    bool curd ;
    if(d[curLeft] > d[curRight]) ans += d[curRight] , curd = 1;
    else ans += d[curLeft] , curd = 0;

    //cout << curd << endl;
    while(1)
    {
        if(curd)
        {
            int newr = walk_left(1 , 1 , n - 1 , curRight + 1 , n - 1 , pref[curLeft - 1]);
            if(newr == -1)
            {
                ans += 2 * pref[n - 1] - pref[curRight];
                break;
            }
            else
            {
                curd ^= 1;
                ans += 2 * pref[newr - 1] - pref[curRight] - pref[curLeft - 1];
                curRight = newr;
            }
        }
        else
        {
            int newl = walk_right(1 , 1 , n - 1 , 1 , curLeft - 1 , pref[curRight]);
            //cout << newl << " " << pref[curRight] << endl;
            if(newl == -1)
            {
                ans += pref[curLeft - 1] + pref[n - 1];
                break;
            }
            else
            {
                ans += pref[curLeft - 1] - 2 * pref[newl] + pref[curRight];
                curd ^= 1;
                curLeft = newl;
            }
        }
    }

    return ans;
}

void solve(void)
{
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> x[i];
    }

    for(int i = 1; i < n; i++)
    {
        d[i] = x[i + 1] - x[i];
        pref[i] = pref[i - 1] + d[i];
    }

    build(1 , 1 , n - 1);

    cin >> q;
    while(q--)
    {
        int st;
        cin >> st;
        int right = lower_bound(x + 1 , x + n + 1 , st) - x;
        int left = right - 1;
        if(right == n + 1)
        {
            cout << abs(st - x[left]) + Query(left) << "\n";
        }
        else if(left == 0)
        {
            cout << abs(st - x[right]) + Query(right) << "\n";
        }
        else if(abs(st - x[left]) <= abs(st - x[right]))
        {
            cout << abs(st - x[left]) + Query(left) << "\n";
        }
        else
        {
            cout << abs(st - x[right]) + Query(right) << "\n";
        }
    }
}
/**
10
1 2 3 4 5 6 7 8 9 10
1
3
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc = 1;
//   cin >> tc;
   while(tc--) solve();

//   execute;
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:228:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
travel.cpp:229:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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