AtCoder Beginner Contest 327 F

https://atcoder.jp/contests/abc327/tasks/abc327_f

かごを下から順にあげていきます。そうしてx方向にスキャンします。
入力例1で、かごの上が1のとき、かごの左が1、2、3が考えられますが、そのときのりんごの数は、[1, 0, 0]です。かごを1上げたとき、(4, 2)にりんごがありますが、そうするとりんごの数が[1, 1, 1]となります。(5, 2)にもリンゴがありますが、そうすると、[1, 1, 2]になります。逆にりんごの数が減る方もあります。このように、ある範囲に1を足すか-1を足す操作をすることになります。
なので、範囲に同じ値を足すことができて、最大値を求めることができる木を適当に作ればよいです。

// Apples
#![allow(non_snake_case)]

use std::cmp::max;


//////////////////// library ////////////////////

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()
}


//////////////////// MaxTree ////////////////////

struct MaxTree {
    a: Vec<i32>,    // max
    w: Vec<i32>     // whole
}

impl MaxTree {
    fn add_core(&mut self, i: usize, d: i32, first: usize, last: usize,
                                first_node: usize, last_node: usize) -> i32 {
        if first <= first_node && last_node <= last {
            self.a[i] += d;
            self.w[i] += d;
            self.a[i]
        }
        else if last_node <= first || last <= first_node {
            self.a[i]
        }
        else {
            let mid = (first_node + last_node) / 2;
            let a1 = self.add_core(i*2+1, d, first, last, first_node, mid);
            let a2 = self.add_core(i*2+2, d, first, last, mid, last_node);
            self.a[i] = max(a1, a2) + self.w[i];
            self.a[i]
        }
    }
    
    fn add(&mut self, d: i32, first: usize, last: usize) -> i32 {
        self.add_core(0, d, first, last, 0, (self.a.len()+1)/2)
    }
    
    fn two_pow(n: usize) -> usize {
        if n <= 2 { n } else { MaxTree::two_pow((n+1)/2)*2 }
    }
    
    fn create(N: usize) -> MaxTree {
        let M = MaxTree::two_pow(N);
        let a: Vec<i32> = vec![0; M*2-1];
        let w: Vec<i32> = vec![0; M*2-1];
        MaxTree { a, w }
    }
}


//////////////////// process ////////////////////

type Point = (usize, usize);

fn read_input() -> (usize, usize, Vec<Point>) {
    let v = read_vec();
    let (N, D, W) = (v[0], v[1], v[2]);
    let points: Vec<Point> = (0..N).map(|_| read_vec::<usize>()).
                                    map(|v| (v[0], v[1])).collect();
    (D, W, points)
}

fn F(D: usize, W: usize, mut points: Vec<Point>) -> i32 {
    let N = points.len();
    points.sort_by(|a, b| a.1.cmp(&b.1));
    let min_x = points.iter().map(|(x, _)| *x).min().unwrap();
    let max_x = points.iter().map(|(x, _)| *x).max().unwrap();
    let mut tree = MaxTree::create(max_x - min_x + 1);
    let mut i: usize = 0;
    let mut j: usize = 0;
    let mut y1: usize = 0;
    let mut max_s: i32 = 0;
    while i < N {
        if y1 >= W && points[j].1 <= y1 - W {
            let x = points[j].0 - min_x;
            tree.add(-1, x, x+D);
            j += 1
        }
        else if points[i].1 <= y1 {
            let x = points[i].0 - min_x;
            y1 = points[i].1;
            let s1 = tree.add(1, x, x+D);
            max_s = max(max_s, s1);
            i += 1
        }
        else {
            y1 += 1
        }
    }
    max_s
}

fn main() {
    let (D, W, points) = read_input();
    println!("{}", F(D, W, points))
}