이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |