Kortit II

use std::{collections::HashSet, io};
 
fn is_valid(sums: &Vec<Vec<Vec<usize>>>, unique_letters: &HashSet<usize>, 
    y_start: usize, x_start: usize, y_end: usize, x_end: usize ) -> bool {
 
        for l in unique_letters {
            let mut count = sums[y_end][x_end][*l];
            if y_start != 0 && x_start != 0 {
                count += sums[y_start-1][x_start-1][*l];
            }
            if y_start != 0 {
                count -= sums[y_start-1][x_end][*l]
            }
            if x_start != 0 {
                count -= sums[y_end][x_start-1][*l];
            }
 
            if count == 0 {
                return false;
            }
        }
 
        return true;
    }
 
fn main() {
    let mut n_str = String::new();
    io::stdin().read_line(&mut n_str).unwrap();
    n_str = n_str.trim().to_string();
    let n: usize = n_str.parse().unwrap();
 
    let mut rows: Vec<Vec<usize>> = Vec::with_capacity(n);
    let mut unique_letters = HashSet::new();
 
    for _ in 0..n {
        let mut row_str = String::new();
        io::stdin().read_line(&mut row_str).unwrap();
        row_str = row_str.trim().to_string();
        rows.push(Vec::with_capacity(n));
 
        for c in row_str.chars() {
            let c_int = (c as usize)-65;
            unique_letters.insert(c_int);
            rows.last_mut().unwrap().push(c_int);
        }
    }
 
    let mut sums: Vec<Vec<Vec<usize>>> = vec![vec![vec![0; 26]; n]; n];
    for row in 0..n {
        for col in 0..n {
            sums[row][col][rows[row][col]] = 1;
            for l in unique_letters.iter() {
                if row != 0 {
                    sums[row][col][*l] += sums[row-1][col][*l];
                }
                if col != 0 {
                    sums[row][col][*l] += sums[row][col-1][*l];
                }
                if row != 0 && col != 0 {
                    sums[row][col][*l] -= sums[row-1][col-1][*l];
                }
            }
        }
    }
 
    let mut count = 0;
 
    'y: for y_start in 0..n {
        for x_start in 0..n {
            if !is_valid(&sums, &unique_letters, y_start, x_start, n-1, n-1) {
                continue 'y;
            }
 
            let mut last_y = y_start;
            let mut x_end = n-1;
 
            loop {
 
                let mut low = last_y;
                let mut high = n-1;
 
                while low < high {
                    let mid = (low + high) / 2;
 
                    if !is_valid(&sums, &unique_letters, y_start, x_start, mid, x_end) {
                        low = mid+1;
                    } else {
                        high = mid;
                    }
                    
                }
 
                if !is_valid(&sums, &unique_letters, y_start, x_start, low, x_end) {
                    break;
                }
                
                last_y = low;
 
                let mut low = x_start;
                let mut high = x_end;
 
                while low < high {
                    let mid = (low + high) / 2;
 
                    if !is_valid(&sums, &unique_letters, y_start, x_start, last_y, mid) {
                        low = mid+1;
                    } else {
                        high = mid;
                    }
                }
                count +=(n-last_y)*(x_end-low+1);
                if low == x_start {
                    break;
                }
                x_end = low-1;
            }
        }
    }
    println!("{}", count);
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 26 but the index is 18446744073709551603', input/code.rs:51:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 2

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 26 but the index is 18446744073709551605', input/code.rs:51:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 3

Group: 3, 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 26 but the index is 18446744073709551600', input/code.rs:51:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 26 but the index is 18446744073709551600', input/code.rs:51:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 5

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 26 but the index is 18446744073709551607', input/code.rs:51:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 6

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 26 but the index is 18446744073709551601', input/code.rs:51:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace