WA on #5 #9 #11 #20

#include<bits/stdc++.h>
using namespace std;
using LD = long double;
using LL = long long;
using ULL = unsigned long long;
#define cr(type) const type &
#define newl '\n'
ostream &out = cout;
istream &in = cin;

const int N = 1e5 + 5, LOG = 18;
int n, logn;

struct city{
    int idx; LL h;
    city(int Idx = 0, LL H = 0){
        idx = Idx, h = H;
    }
    friend bool operator<(cr(city) a, cr(city) b){
        return a.h < b.h;
    }
};
set<city> st;
int cmp[5]; 
int nxtA[N], nxtB[N], f[LOG][N][2]; LL h[N], da[LOG][N][2], db[LOG][N][2];

inline LL dist(int i, int j){
    return abs(h[i] - h[j]);
}

pair<LL, LL> calc(int s, int x){
    LL la = 0, lb = 0;
    for(int i = logn; i >= 0; i--){
        if(!f[i][s][0]) continue;
        if(la + lb + da[i][s][0] + db[i][s][0] <= x){
            la += da[i][s][0], lb += db[i][s][0];
            s = f[i][s][0];
        }
    }
    return make_pair(la, lb);
}

int main(){
    ios::sync_with_stdio(0), in.tie(0), out.tie(0);
    in >> n;
    for(int i = 1; i <= n; i++) in >> h[i];
    st.insert(city(n, h[n]));
    for(int i = n - 1; i; i--){
        int tot = 0;
        auto nxt = st.upper_bound(city(i, h[i]));
        auto pre = st.lower_bound(city(i, h[i]));
        if(nxt != st.end()) cmp[++tot] = nxt->idx;
        if(++nxt != st.end()) cmp[++tot] = nxt->idx;
        if(pre != st.begin()) cmp[++tot] = (--pre)->idx;
        if(pre != st.begin()) cmp[++tot] = (--pre)->idx;
        sort(cmp + 1, cmp + tot + 1, [&](cr(int) a, cr(int) b){ 
            if(dist(i, a) != dist(i, b)) return dist(i, a) < dist(i, b);
            return h[a] < h[b];
        });
        if(tot >= 1) nxtB[i] = cmp[1];
        if(tot >= 2) nxtA[i] = cmp[2];
        st.insert(city(i, h[i]));
    }
    logn = ceil(log2(n));
    for(int i = 1; i <= n; i++){
        f[0][i][0] = nxtA[i], f[0][i][1] = nxtB[i];
    }
    for(int i = 1; i <= n; i++){
        f[1][i][0] = f[0][f[0][i][0]][1];
        f[1][i][1] = f[0][f[0][i][1]][0];
    }
    for(int k = 2; k <= logn; k++){
        for(int i = 1; i <= n; i++){
            f[k][i][0] = f[k - 1][f[k - 1][i][0]][0];
            f[k][i][1] = f[k - 1][f[k - 1][i][1]][1];
        }
    }
    memset(da, 0x3f, sizeof da);
    memset(db, 0x3f, sizeof db);
    for(int i = 1; i <= n; i++){
        if(nxtA[i]) da[0][i][0] = dist(i, nxtA[i]);
        da[0][i][1] = 0;
        db[0][i][0] = 0;
        if(nxtB[i]) db[0][i][1] = dist(i, nxtB[i]);
    }
    for(int i = 1; i <= n; i++){
        da[1][i][0] = da[0][i][0];
        da[1][i][1] = da[0][f[0][i][1]][0];
        db[1][i][0] = db[0][f[0][i][0]][1];
        db[1][i][1] = db[0][i][1];   
    }
    for(int k = 2; k <= logn; k++){
        for(int i = 1; i <= n; i++){
            da[k][i][0] = da[k - 1][i][0] + da[k - 1][f[k - 1][i][0]][0];
            da[k][i][1] = da[k - 1][i][1] + da[k - 1][f[k - 1][i][1]][1];
            db[k][i][0] = db[k - 1][i][0] + db[k - 1][f[k - 1][i][0]][0];
            db[k][i][1] = db[k - 1][i][1] + db[k - 1][f[k - 1][i][1]][1];
        }
    }
    
    int x0;
    in >> x0;
    int s0 = 0; pair<LL, LL> best;
    for(int i = 1; i <= n; i++){
        auto res = calc(i, x0);
        if(!s0) s0 = i, best = res;
        else{
            if(res.second == 0){
                if(best.second == 0 && h[i] > h[s0]) s0 = i, best = res; 
            }
            else{
                bool flag = best.second == 0;
                if(!flag) flag |= (double)res.first / res.second < (double)best.first / best.second;
                flag |= (double)res.first / res.second == (double)best.first / best.second && h[i] > h[s0];
                if(flag){
                    s0 = i, best = res;
                }
            }
        }
    }
    out << s0 << newl;
    int m;
    in >> m;
    while(m--){
        int s, x;
        in >> s >> x;
        auto res = calc(s, x);
        out << res.first << ' ' << res.second << newl;
    }
    return 0;
}