제출 #917164

#제출 시각아이디문제언어결과실행 시간메모리
917164huutuanBitaro's travel (JOI23_travel)C++14
100 / 100
169 ms20744 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define isz(x) ((int)x.size()) #define sumof(x) accumulate(all(x), 0ll) const int N=2e5+10, inf=1e18; struct Node{ int val1, val2; Node (int t1=0, int t2=0){ val1=t1; val2=t2; } Node operator+(Node &b){ return Node(max(val1, b.val1), min(val2, b.val2)); } }; struct SegmentTree{ int n; vector<Node> t; void init(int _n){ n=_n; t.assign(4*n+1, Node()); } void build(int k, int l, int r, int *a){ if (l==r){ t[k]=Node(a[l]*2-a[l-1], a[l]*2-a[l+1]); return; } int mid=(l+r)>>1; build(k<<1, l, mid, a); build(k<<1|1, mid+1, r, a); t[k]=t[k<<1]+t[k<<1|1]; } int walk1(int k, int l, int r, int pos, int val){ if (t[k].val1<=val || l>pos) return 1; if (l==r) return l; int mid=(l+r)>>1; if (t[k<<1|1].val1<=val) return walk1(k<<1, l, mid, pos, val); int tmp=walk1(k<<1|1, mid+1, r, pos, val); if (tmp==1) return walk1(k<<1, l, mid, pos, val); return tmp; } int walk2(int k, int l, int r, int pos, int val){ if (t[k].val2>val || r<pos) return n; if (l==r) return l; int mid=(l+r)>>1; if (t[k<<1].val2>val) return walk2(k<<1|1, mid+1, r, pos, val); int tmp=walk2(k<<1, l, mid, pos, val); if (tmp==n) return walk2(k<<1|1, mid+1, r, pos, val); return tmp; } } st; int n, q, a[N]; void solve(){ cin >> n; for (int i=1; i<=n; ++i) cin >> a[i]; cin >> q; a[0]=-inf, a[n+1]=inf; st.init(n); st.build(1, 1, n, a); while (q--){ int s; cin >> s; int ir=lower_bound(a+1, a+n+1, s)-a; int il=ir-1; int cur=s, ans=0; while (il>=1 || ir<=n){ if (il>=1 && (ir>n || abs(cur-a[il])<=abs(cur-a[ir]))){ int i=st.walk1(1, 1, n, il, a[ir]); ans+=abs(cur-a[i]); il=i-1; cur=a[i]; // dist(i, i-1) > dist(i, ir) // a[i] - a[i-1] > a[ir] - a[i] // 2 a[i] - a[i-1] > a[ir] // tim i dau tien <= il }else{ int i=st.walk2(1, 1, n, ir, a[il]); ans+=abs(cur-a[i]); ir=i+1; cur=a[i]; // dist(il, i) <= dist(i, i+1) // a[i] - a[il] <= a[i+1] - a[i] // 2a[i] - a[i+1] <= a[il] // tim i dau tien >= ir } } cout << ans << '\n'; } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int ntests=1; // cin >> ntests; for (int i=1; i<=ntests; ++i) solve(); 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...