Submission #1006703

#TimeUsernameProblemLanguageResultExecution timeMemory
1006703snpmrnhlolBitaro's travel (JOI23_travel)C++17
100 / 100
672 ms7252 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5; int v[N]; int n; int lb(int nr){ int l = 0,r = n; while(l != r){ int mij = (l + r)/2; if(v[mij] >= nr)r = mij; else l = mij + 1; } return l; } int main(){ cin>>n; for(int i = 0;i < n;i++){ cin>>v[i]; } int q; cin>>q; for(int i = 0;i < q;i++){ int x; cin>>x; ll ans = 0; int l,r,pos; int tmp; tmp = lb(x); if(tmp != 0 && (tmp == n || x - v[tmp - 1] <= v[tmp] - x)){ ans+=x - v[tmp - 1]; l = tmp - 1;r = tmp - 1; }else{ ans+=v[tmp] - x; l = tmp;r = tmp; } pos = 0; while(l != 0 || r != n - 1){ if(l == 0 || r == n - 1){ ///go to n - 1 ans+=v[n - 1] - v[0]; l = 0; r = n - 1; continue; } if(pos == 0){ tmp = lb(v[l] - (v[r + 1] - v[l])); if(tmp == l){ ///bad go to r + 1 pos = 1; ans+=v[r + 1] - v[l]; r++; }else{ pos = 0; ans+=v[l] - v[tmp]; l = tmp; } }else{ tmp = lb(v[r] + (v[r] - v[l - 1])) - 1; if(tmp == r){ pos = 0; ans+=v[r] - v[l - 1]; l--; }else{ pos = 1; ans+=v[tmp] - v[r]; r = tmp; } } } cout<<ans<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...