TOCPC2021: Long Jump

#include <bits/stdc++.h>
using namespace std;

#define r first
#define c second
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;

const int N = 1e6 + 5;
const pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, -1), pii(0, 1)}; // U D L R

enum direction {
    UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3
};

map<pii, int> ed;
set<pii> visited;
vector<int> adj[2][N];

pii moveToWall(pii st, int d){
    pii ans = pii(0, 0);
    if(d == UP){
        ans.c = st.c;
        ans.r = *(lower_bound(adj[1][st.c].begin(), adj[1][st.c].end(), st.r) - 1);
    } else if(d == DOWN){
        ans.c = st.c;
        ans.r = *upper_bound(adj[1][st.c].begin(), adj[1][st.c].end(), st.r);
    } else if(d == LEFT){
        ans.r = st.r;
        ans.c = *(lower_bound(adj[0][st.r].begin(), adj[0][st.r].end(), st.c) - 1);
    } else if(d == RIGHT){
        ans.r = st.r;
        ans.c = *upper_bound(adj[0][st.r].begin(), adj[0][st.r].end(), st.c);
    }
    return pii(ans.r - dir[d].r, ans.c - dir[d].c);
}

int main(){

    int row, col, nWall;
    pii st, ed;
    scanf("%d%d%d%d%d%d%d", &row, &col, &nWall, &st.r, &st.c, &ed.r, &ed.c);
    for(int i = 1; i <= nWall; ++i){
        int r, c;
        scanf("%d%d", &r, &c);
        adj[0][r].push_back(c);
        adj[1][c].push_back(r);
    }
    for(int i = 1; i <= row; ++i){
        if(!adj[0][i].empty()){
            adj[0][i].push_back(0);
            sort(adj[0][i].begin(), adj[0][i].end());
            adj[0][i].push_back(col + 1);
        } else {
            adj[0][i].push_back(0);
            adj[0][i].push_back(col + 1);
        }
    }
    for(int j = 1; j <= col; ++j){
        if(!adj[1][j].empty()){
            adj[1][j].push_back(0);
            sort(adj[1][j].begin(), adj[1][j].end());
            adj[1][j].push_back(row + 1);
        } else {
            adj[1][j].push_back(0);
            adj[1][j].push_back(row + 1);
        }
    }
    queue<ppi> que;
    visited.insert(ed);
    que.emplace(ed, 0);
    while(!que.empty()){
        pii u = que.front().r;
        int dist = que.front().c;
        que.pop();
        if(u == st){
            cout << dist;
            return 0;
        }
        for(int d = 0; d < 4; ++d){
            pii v = moveToWall(u, d);
            if(visited.find(v) == visited.end()){
                visited.insert(v);
                que.emplace(v, dist + 1);
            }
        }
    }
    cout << "-1";

    return 0;
}