Submission #792537

#	Time	Username	Problem	Language	Result	Execution time	Memory
792537		vjudge1	Bitaro's travel (JOI23_travel)	C++17	15 / 100	3072 ms	52344 KiB

travel

// Author : حسن

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 2e5 + 9 , mod = 1e9 + 7;
ll c[N] = {} , d[N] = {} , a[N] = {}, b[N] = {} ;

void solve(){
    ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
    set<pair<ll,ll>>st , st1 , st2 , st3;
    cin>>n;
    for(i = 1;i <= n; i++){
        cin>>a[i];
        st.insert({a[i] , -i});
        st1.insert({a[i] , i});
    }
    cin>>q;
    st2 = st , st3 = st1;
    while(q--){
        cin>>k;
        st = st2 , st1 = st3;
        s =0;
        while(st.size()){
            x = y = -1;
            auto it = st.lower_bound({k , -1e9});
            auto it1 = st1.lower_bound({k , -1e9});
            if(it1 != st1.end())
                x = it1->se;
            if(it != st.begin()){
                it--;
                y = -it->se;
            }
            if(x != -1 && y != -1){
                if((abs(a[y] - k) < abs(a[x] - k)) || (abs(a[y] - k) == abs(a[x] - k) && y < x))
                    swap(y , x);
                s += abs(a[x] - k) , k = a[x] , st.erase({a[x] , -x}) , st1.erase({a[x] , x});
            }else {
            if(x == -1)
                swap(x , y);
            s += abs(a[x] - k) , k = a[x] , st.erase({a[x] , -x}) , st1.erase({a[x] , x});
            }
        }
        cout<<s<<"\n";
    }
}

int main(){
    /*
     TL;
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

travel.cpp: In function 'void solve()':
travel.cpp:31:16: warning: unused variable 'j' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
travel.cpp:31:20: warning: unused variable 'm' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                    ^
travel.cpp:31:28: warning: unused variable 'z' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                            ^
travel.cpp:31:40: warning: unused variable 'f' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                        ^
travel.cpp:31:43: warning: unused variable 'l' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                           ^
travel.cpp:31:47: warning: unused variable 'r' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                               ^
travel.cpp:31:63: warning: unused variable 'mn' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                               ^~
travel.cpp:31:76: warning: unused variable 'mx' [-Wunused-variable]
   31 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                            ^~

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