Submission #56326037

---

Source Code Expand

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 200005;

int n,y[maxn][2],mny[18][maxn],mxy[18][maxn];

int jump(int sx, int tx, int sy){
    int len = 1;
    for(int b = 17;b >= 0;--b){
        int sz = (1 << b);
        if(sx + len + sz - 1 <= tx){
            if(mny[b][sx + len] <= sy && sy <= mxy[b][sx + len]){
                len += sz;
            }
        }
    }
    return sx + len - 1;
}

struct Data{
    int x,id;
    long long c;
};

Data go[18][maxn][2];

int main(){
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> y[i][0] >> y[i][1];
    }
    for(int i = 0;i < n;++i){
        mny[0][i] = y[i][0];
        mxy[0][i] = y[i][1];
    }
    for(int b = 1;b < 18;++b){
        int sz = (1 << b);
        int szh = (1 << (b - 1));
        for(int i = 0,mi = i + szh;i + sz - 1 < n;++i, ++mi){
            mny[b][i] = max(mny[b - 1][i], mny[b - 1][mi]);
            mxy[b][i] = min(mxy[b - 1][i], mxy[b - 1][mi]);
        }
    }
    for(int i = 0;i < n;++i){
        for(int j = 0;j < 2;++j){
            int res = jump(i, n - 1, y[i][j]);
            go[0][i][j] = {res + 1, 0, 0};
            if(res < n - 1){
                if(y[i][j] < y[res + 1][0]){
                    go[0][i][j].id = 0;
                    go[0][i][j].c = y[res + 1][0] - y[i][j];
                }else{
                    go[0][i][j].id = 1;
                    go[0][i][j].c = y[i][j] - y[res + 1][1];
                }
            }
        }
    }
    for(int b = 1;b < 18;++b){
        for(int i = 0;i < n;++i){
            for(int j = 0;j < 2;++j){
                if(go[b - 1][i][j].x < n - 1){
                    auto &[x, id, c] = go[b - 1][i][j];
                    auto aux = go[b - 1][x][id];
                    go[b][i][j] = {aux.x, aux.id, c + aux.c};
                }else{
                    go[b][i][j] = {n, 0, 0};
                }
            }
        }
    }
    int nq,sx,sy,tx,ty;
    cin >> nq;
    while(nq--){
        cin >> sx >> sy >> tx >> ty;
        --sx; --tx;
        if(sx == tx){
            cout << abs(sy - ty) << '\n';
            continue;
        }
        if(sx > tx){
            swap(sx, tx);
            swap(sy, ty);
        }
        int tox = jump(sx, tx, sy);
        long long ans = tx - sx;
        if(tox != tx){
            int cur_x = tox + 1,cur_id;
            if(sy < y[cur_x][0]){
                cur_id = 0;
                ans += y[cur_x][0] - sy;
            }else{
                cur_id = 1;
                ans += sy - y[cur_x][1];
            }
            for(int b = 17;b >= 0;--b){
                auto &[x, id, cost] = go[b][cur_x][cur_id];
                if(x <= tx){
                    cur_x = x;
                    cur_id = id;
                    ans += cost;
                }
            }
            ans += abs(y[cur_x][cur_id] - ty);
        }else{
            ans += abs(ty - sy);
        }
        cout << ans << '\n';
    }
    return 0;
}

Submission Info

Judge Result