Submission #972493

#	Time	Username	Problem	Language	Result	Execution time	Memory
972493		vjudge1	Bitaro's travel (JOI23_travel)	C++17	45 / 100	457 ms	45552 KiB

travel

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

int tt = 1, n;
ll a[200005], dist, x[200005];
set<ll> st;
bool ok = 0;
ll pref[200005], suff[200005];
map<ll, ll> mp;
set<pair<ll, ll>> st1;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        st.insert(a[i]);
        st1.insert({a[i], i});
        if(i > 1 && a[i] - a[i - 1] > 100) ok = 1;
        mp[a[i]] = i;
    }
    cin >> tt;
    if(!ok){
        for(int i = 2; i <= n; i++)
            pref[i] = pref[i - 1] + (a[i] - a[i - 1]);
        for(int i = n - 1; i >= 1; i--)
            suff[i] = suff[i + 1] + (a[i + 1] - a[i]);
        while(tt--){
            ll pos, p1, p2, sum = 0;
            cin >> pos;
            if(pos <= a[1]){
                cout << a[n] - pos << "\n";
                continue;
            }
            if(pos >= a[n]){
                cout << pos - a[1] << "\n";
                continue;
            }
            int pos2 = *st.lower_bound(pos);
            auto it = st.lower_bound(pos);
            it--;
            int pos1 = *it;
            int t = 0;
            bool f = 0;
            pos1 = mp[pos1];
            pos2 = mp[pos2];
            if(pos - a[pos1] <= a[pos2] - pos){
                sum = pos - a[pos1];
                pos = a[pos1];
                pos1--;
            }
            else{
                sum = a[pos2] - pos;
                pos = a[pos2];
                pos2++;
                f = 1;
            }
            while(pos1 >= 1 && pos2 <= n && a[pos2] - pos <= 100 && pos - a[pos1] <= 100){
                if(abs(pos - a[pos1]) <= abs(pos - a[pos2])){
                    sum += abs(pos - a[pos1]);
                    pos = a[pos1];
                    pos1--;
                    f = 0;
                }
                else{
                    sum +=  abs(pos - a[pos2]);
                    pos = a[pos2];
                    pos2++;
                    f = 1;
                }
            }
            if(!f){
                if(pos1 > 0) sum += (pos - a[1]);
                if(pos2 != n + 1) sum += (a[n] - a[1]); 
            }
            else{
                if(pos2 <= n) sum += (a[n] - pos);
                if(pos1 > 0) sum += (a[n] - a[1]);
            }
            cout << sum << "\n";
        }
    }
    else{
        for(int i = 1; i <= tt; i++){
            cin >> x[i];
            ll sum = 0, pos = x[i];
            while(!st1.empty()){
                ll x1 = 1e10, y1 = 1e10;
                pair<ll, int> p1, p2;
                if(st1.begin()->first <= pos){
                    auto it = st1.lower_bound({pos, 0});
                    it--;
                    x1 = pos - it->first;
                    p1 = *it;
                }
                if(st1.rbegin()->first > pos){
                    auto it = st1.upper_bound({pos, 0});
                    y1 = it->first - pos;
                    p2 = *it;
                }
                if(x1 <= y1){
                    sum += x1;
                    pos -= x1;
                    st1.erase(p1);
                }   
                else{
                    sum += y1;
                    pos += y1;
                    st1.erase(p2);
                }
            }
            cout << sum << "\n";
        }
    }
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:55:21: warning: unused variable 'p1' [-Wunused-variable]
   55 |             ll pos, p1, p2, sum = 0;
      |                     ^~
travel.cpp:55:25: warning: unused variable 'p2' [-Wunused-variable]
   55 |             ll pos, p1, p2, sum = 0;
      |                         ^~
travel.cpp:69:17: warning: unused variable 't' [-Wunused-variable]
   69 |             int t = 0;
      |                 ^

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