AtCoder Beginner Contest 273 D

https://atcoder.jp/contests/abc273/tasks/abc273_d

これも行と列で分けて考えることができます。
壁の座標を各行、各列で格納します。
その際に二分探索をするのでソートしますが、HashMapの中のVecをどうソートしていいのか分からなかったので、新たにHashMapを構築しました。

// LRUD Instructions
#![allow(non_snake_case)]

use std::collections::HashMap;
use std::cmp::min;
use std::cmp::max;

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

struct Point {
    x: i32,
    y: i32,
}

fn read_point() -> Point {
    let v: Vec<i32> = read::<String>().split_whitespace()
                    .map(|e| e.parse().ok().unwrap()).collect();
    Point { x: v[1], y: v[0] }
}

fn read_input() -> (i32, i32, Point, Vec<Point>, Vec<(char, i32)>) {
    let v = read_vec();
    let H: i32 = v[0];
    let W: i32 = v[1];
    let pt0 = Point { x: v[3], y: v[2] };
    let N: i32 = read();
    let walls: Vec<Point> = (0..N).map(|_| read_point()).collect();
    let Q: i32 = read();
    let queries: Vec<(char, i32)> = (0..Q).map(|_| read_vec::<String>()).
                map(|v| (v[0].chars().next().unwrap(), v[1].parse().unwrap())).
                collect();
    (H, W, pt0, walls, queries)
}

struct Walls {
    walls: Vec<i32>
}

impl Walls {
    fn push(&mut self, x: i32) {
        self.walls.push(x)
    }
    
    fn find_range(&self, x: i32, first: usize, last: usize) -> usize {
        if first == last - 1 {
            first
        }
        else {
            let mid = (first + last) / 2;
            if x < self.walls[mid] {
                self.find_range(x, first, mid)
            }
            else {
                self.find_range(x, mid, last)
            }
        }
    }
    
    fn walk_x(&self, x: i32, n: i32) -> i32 {
        let first = self.find_range(x, 0, self.walls.len() - 1);
        if n > 0 {
            let upper = self.walls[first+1] - 1;
            min(upper, x + n)
        }
        else {
            let lower = self.walls[first] + 1;
            max(lower, x + n)
        }
    }
}

struct Board {
    H: i32,
    W: i32,
    HWalls: HashMap<i32, Walls>,
    VWalls: HashMap<i32, Walls>,
}

impl Board {
    fn walk(&self, pt: Point, query: &(char, i32)) -> Point {
        match *query {
            ('L', n) => self.walk_x(pt, -n),
            ('R', n) => self.walk_x(pt,  n),
            ('U', n) => self.walk_y(pt, -n),
            ('D', n) => self.walk_y(pt,  n),
            _   => pt
        }
    }
    
    fn walk_x(&self, pt: Point, n: i32) -> Point {
        match self.HWalls.get(&pt.y) {
            Some(walls) => Point { x: walls.walk_x(pt.x, n), y: pt.y },
            None        => {
                if n > 0 {
                    Point { x: min(pt.x + n, self.W), y: pt.y }
                } else { 
                    Point { x: max(pt.x + n, 1), y: pt.y }
                }
            }
        }
    }
    
    fn walk_y(&self, pt: Point, n: i32) -> Point {
        match self.VWalls.get(&pt.x) {
            Some(walls) => Point { x: pt.x, y: walls.walk_x(pt.y, n) },
            None        => {
                if n > 0 {
                    Point { x: pt.x, y: min(pt.y + n, self.H) }
                }
                else {
                    Point { x: pt.x, y: max(pt.y + n, 1) }
                }
            }
        }
    }
    
    fn create(H: i32, W: i32, walls: &Vec<Point>) -> Board {
        let mut walls1 = HashMap::<i32, Walls>::new();
        let mut walls2 = HashMap::<i32, Walls>::new();
        for wall in walls.iter() {
            let v = walls1.entry(wall.y).or_insert(Walls { walls: vec![] });
            v.push(wall.x);
            let w = walls2.entry(wall.x).or_insert(Walls { walls: vec![] });
            w.push(wall.y);
        }
        
        let HWalls = Board::sort(walls1, W);
        let VWalls = Board::sort(walls2, H);
        
        Board { H, W, HWalls, VWalls }
    }
    
    fn sort(walls: HashMap<i32, Walls>, U: i32) -> HashMap<i32, Walls> {
        let mut sorted_walls = HashMap::<i32, Walls>::new();
        for (&y, wall) in &walls {
            let mut xs1 = wall.walls.iter().map(|&x| x).collect::<Vec::<i32>>();
            xs1.sort();
            xs1.insert(0, 0);
            xs1.push(U + 1);
            sorted_walls.insert(y, Walls { walls: xs1 });
        }
        sorted_walls
    }
}

fn f(H: i32, W: i32, pt0: Point, walls: Vec<Point>,
                                queries: Vec<(char, i32)>) {
    let board = Board::create(H, W, &walls);
    let mut pt = pt0;
    for query in queries.iter() {
        pt = board.walk(pt, query);
        println!("{} {}", pt.y, pt.x)
    }
}

fn main() {
    let v = read_input();
    f(v.0, v.1, v.2, v.3, v.4)
}