Ruudukko

use std::{io::stdin, collections::BinaryHeap};

const MODULUS: u64 = 10_u64.pow(9) + 7;

// This took me way too long to solve

struct Grid {
    n: u32,
    relaxed_rows: Vec<(u64, u64, u32)>,
    relaxed_columns: Vec<(u64, u64, u32)>,
}

impl Grid {
    fn idx(&self, x: u32, y: u32) -> usize {
        (x + self.n * y) as usize
    }

    #[must_use]
    fn relax(&mut self, x: u32, y: u32, value: u32) -> Option<()> {
        let (row_sum, row_last_addition, row_last_value) = self.relaxed_rows.get_mut(y as usize)?;
        let (col_sum, col_last_addition, col_last_value) = self.relaxed_columns.get_mut(x as usize)?;

        let row_addition = if *row_last_value == value {
            *row_last_addition
        } else {
            *row_sum
        };
        let col_addition = if *col_last_value == value {
            *col_last_addition
        } else {
            *col_sum
        };
        let addition = 1 + row_addition + col_addition;

        *row_sum += addition;
        *col_sum += addition;

        *row_sum %= MODULUS;
        *col_sum %= MODULUS;

        *row_last_value = value;
        *col_last_value = value;

        *row_last_addition = row_addition;
        *col_last_addition = col_addition;

        Some(())
    }
}

#[derive(Eq, PartialEq)]
struct Node {
    value: u32,
    i: u32,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.value.cmp(&self.value)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let n: u32 = buf.trim().parse().unwrap();

    let mut grid = Grid {
        n,
        relaxed_rows: vec![(0, 0, 0); n as usize],
        relaxed_columns: vec![(0, 0, 0); n as usize],
    };

    let mut q = BinaryHeap::new();

    for y in 0..n {
        buf.clear();
        stdin().read_line(&mut buf).unwrap();

        for (x, value) in buf.split_whitespace().enumerate() {
            let value: u32 = value.parse().unwrap();
            q.push(Node {
                value,
                i: grid.idx(x as u32, y) as u32,
            });
        }
    }

    while let Some(next) = q.pop() {
        let x = next.i % n;
        let y = next.i / n;
        grid.relax(x, y, next.value).unwrap();
    }

    let sum: u64 = grid.relaxed_rows.iter()
        .fold(0, |sum, (value, _, _)| (sum + value) % MODULUS);

    println!("{}", sum % MODULUS);
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED