Submission #917164

#	Time	Username	Problem	Language	Result	Execution time	Memory
917164		huutuan	Bitaro's travel (JOI23_travel)	C++14	100 / 100	169 ms	20744 KiB

travel

#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;
}

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