Submission #972480

#	Time	Username	Problem	Language	Result	Execution time	Memory
972480		vjudge1	Bitaro's travel (JOI23_travel)	C++17	0 / 100	339 ms	31344 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;
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]);
        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;
            deque<pair<ll, int>> d1, d2;
            if(pos <= a[1]){
                cout << a[n] - pos << "\n";
                continue;
            }
            if(pos >= a[n]){
                cout << pos - a[1] << "\n";
                continue;
            }
            int pos1 = *st.lower_bound(pos);
            auto it = st.lower_bound(pos);
            it--;
            int pos2 = *it;
            int t = 0;
            bool f = 0;
            swap(pos1, pos2);
            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] - 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";
        }
    }
}

Compilation message (stderr)

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

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