Submission #972464

#	Time	Username	Problem	Language	Result	Execution time	Memory
972464		vjudge1	Bitaro's travel (JOI23_travel)	C++17	15 / 100	3074 ms	20640 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<pair<ll, int>> st;
bool ok = 0;
ll pref[200005], suff[200005];
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], i});
        if(i > 1 && a[i] - a[i - 1] > 100) ok = 1;
    }
    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;
            deque<pair<ll, int>> d1, d2;
            if(a[1] <= pos){
                auto it = st.upper_bound({pos + 1, 0});
                it--;
                p1 = it->second;
                for(int i = p1; i >= 1; i--)
                    if(abs(pos - a[i]) <= 100) d1.push_front({a[i], i});    
            }
            if(a[n] > pos){
                auto it = st.upper_bound({pos + 1, 0});
                p2 = it->second;
                for(int i = p2; i <= n; i++)
                    if(abs(a[i] - pos) <= 100) d2.push_back({a[i], i});
            }
            if(d1.empty() || d2.empty()){
                if(pos <= a[1]) cout << pref[n] + a[1] - pos << "\n";
                else cout << suff[1] + pos - a[n] << "\n";
                continue;
            }
            int pos1 = d1.back().second, pos2 = d2.front().second;
            int t = 0;
            while(pos1 >= 1 && pos2 <= n){
                if(abs(pos - a[pos1]) <= abs(pos - a[pos2])){
                    sum += abs(pos - a[pos1]);
                    pos = a[pos1];
                    pos1--;
                }
                else{
                    sum +=  abs(pos - a[pos2]);
                    pos = a[pos2];
                    pos2++;
                }
                if(pos1 < 1 || pos2 > n){
                    t = -1;
                    break;
                }
                if(a[pos2] - pos > 100){
                    t = 1;
                    break;
                }
                if(pos - a[pos1] > 100){
                    break;
                }
            }
            if(t == -1){
                if(pos1 == 0) cout << sum + (a[n] - pos) << "\n";
                else cout << sum + (pos - a[1]) << "\n";
                continue;
            }
            if(t == 1){
                cout << sum + (pos1 - a[1]) + (a[n] - a[1]) << "\n";
                continue;
            }
            else{
                cout << sum + (a[n] - pos) + (a[n] - a[1]) << "\n";
                continue;
            }
        }
    }
    for(int i = 1; i <= tt; i++){
        cin >> x[i];
        ll sum = 0, pos = x[i];
        while(!st.empty()){
            ll x1 = 1e10, y1 = 1e10;
            pair<ll, int> p1, p2;
            if(st.begin()->first <= pos){
                auto it = st.lower_bound({pos, 0});
                it--;
                x1 = pos - it->first;
                p1 = *it;
            }
            if(st.rbegin()->first > pos){
                auto it = st.upper_bound({pos, 0});
                y1 = it->first - pos;
                p2 = *it;
            }
            if(x1 <= y1){
                sum += x1;
                pos -= x1;
                st.erase(p1);
            }   
            else{
                sum += y1;
                pos += y1;
                st.erase(p2);
            }
        }
        cout << sum << "\n";
    }
}

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