Ruudukko

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

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

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

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

    fn value(&self, x: u32, y: u32) -> Option<u32> {
        self.data.get(self.idx(x, y)).copied()
    }

    #[must_use]
    fn relax(&mut self, x: u32, y: u32) -> Option<()> {
        let this_value = self.value(x, y)?;

        let my_row = self.relaxed_rows.get_mut(y as usize)?;
        let my_col = self.relaxed_columns.get_mut(x as usize)?;

        if this_value == 1 {
            let this = (1, 1);
            my_col.push(this);
            my_row.push(this);
            return Some(());
        }

        let mut sum = 1;
        for &(other_value, other_sum) in &*my_row {
            if other_value < this_value {
                sum += other_sum;
            }
        }
        for &(other_value, other_sum) in &*my_col {
            if other_value < this_value {
                sum += other_sum;
            }
        }

        let this = (this_value, sum % MODULUS);
        my_col.push(this);
        my_row.push(this);

        Some(())
    }
}

#[derive(Eq, PartialEq)]
struct Node {
    value: u32,
    x: u32,
    y: 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,
        data: Vec::with_capacity((n * n) as usize),
        relaxed_rows: vec![vec![]; n as usize],
        relaxed_columns: vec![vec![]; 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();
            grid.data.push(value);
            q.push(Node {
                value,
                x: x as u32,
                y,
            });
        }
    }

    while let Some(next) = q.pop() {
        grid.relax(next.x, next.y).unwrap();
    }

    let sum: u64 = grid.relaxed_rows.iter()
        .flatten()
        .map(|(_, v)| v)
        .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: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED