제출 #792742

#제출 시각아이디문제언어결과실행 시간메모리
792742vjudge1Bitaro's travel (JOI23_travel)C++14
100 / 100
331 ms22596 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std ; const ll N = 2e5 ; ll n, q, x[N + 2], abu[N + 2] ; bool flag ; signed main() { ios_base::sync_with_stdio( 0 ) ; cin.tie( 0 ) ; cout.tie( 0 ) ; cin >> n ; x[0] = -1e18 ; x[n + 1] = 1e18 ; for(ll i = 1 ; i <= n ; i++) cin >> x[i] ; for(ll i = 1 ; i < n ; i++) if(x[i + 1] - x[i] > 100) flag = 1 ; cin >> q ; if(q == 1) { ll ans = 0, pos ; cin >> pos ; set<ll> s_neg, s_pos ; for(ll i = 1 ; i <= n ; i++) s_pos.insert(x[i]), s_neg.insert(-x[i]) ; while(s_pos.size()) { ll l = -1e18, r = 1e18 ; if(s_pos.lower_bound(pos) != s_pos.end()) r = *s_pos.lower_bound(pos) ; if(s_neg.lower_bound(-pos) != s_neg.end()) l = -(*s_neg.lower_bound(-pos)) ; if(pos - l <= r - pos) { ans += pos - l ; pos = l ; s_neg.erase(-l) ; s_pos.erase(l) ; } else { ans += r - pos ; pos = r ; s_neg.erase(-r) ; s_pos.erase(r) ; } } cout << ans ; return 0 ; } // if(!flag) // { // for(ll i = 1 ; i <= n ; i++) // { // ll l = i - 1, r = i + 1, now = i ; // while(x[now] - x[l] <= 100ll && x[r] - x[now] <= 100ll) // if(x[now] - x[l] <= x[r] - x[now]) // { // abu[i] += x[now] - x[l] ; // now = l ; // l-- ; // } // else // { // abu[i] += x[r] - x[now] ; // now = r ; // r++ ; // } // if(l && r <= n) // { // if(x[now] - x[l] <= 100) // abu[i] += x[now] - x[1] ; // else // abu[i] += x[n] - x[now] ; // } // abu[i] += x[n] - x[1] ; // } // while(q--) // { // ll pos, l = 0, r = n + 1 ; // cin >> pos ; // while(l + 1 < r) // { // ll mid = (l + r) >> 1 ; // if(x[mid] <= pos)l = mid ; // else r = mid ; // } // if(pos - x[l] <= x[r] - pos) // cout << abu[l] + pos - x[l] ; // else // cout << abu[r] + x[r] - pos ; // cout << '\n' ; // } // } // else // { for(ll i = 1 ; i <= n ; i++) { ll l = i - 1, r = i + 1, now = i ; while(l && r <= n) if(x[now] - x[l] <= x[r] - x[now]) { ll l1 = 0, r1 = l ; while(l1 + 1 < r1) { ll mid = (l1 + r1) >> 1 ; if(x[now] - x[mid] <= x[r] - x[now])r1 = mid ; else l1 = mid ; } abu[i] += x[now] - x[r1] ; now = r1 ; l = r1 - 1 ; } else { ll l1 = r, r1 = n + 1 ; while(l1 + 1 < r1) { ll mid = (l1 + r1) >> 1 ; if(x[now] - x[l] > x[mid] - x[now])l1 = mid ; else r1 = mid ; } abu[i] += x[l1] - x[now] ; now = l1 ; r = l1 + 1 ; } abu[i] += x[n] - x[1] ; } while(q--) { ll pos, l = 0, r = n + 1 ; cin >> pos ; while(l + 1 < r) { ll mid = (l + r) >> 1 ; if(x[mid] <= pos)l = mid ; else r = mid ; } if(pos - x[l] <= x[r] - pos) cout << abu[l] + pos - x[l] ; else cout << abu[r] + x[r] - pos ; cout << '\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...