Ruudukko

//package com.patonki;

import java.io.*;
import java.util.*;

class Pair implements Comparable<Pair>{
    int value;
    int y;
    int x;

    public Pair(int value, int y, int x) {
        this.value = value;
        this.y = y;
        this.x = x;
    }

    @Override
    public int compareTo(Pair o) {
        int val = Integer.compare(value,o.value);
        if (val != 0) return val;

        int y = Integer.compare(this.y,o.y);
        if (y != 0) return y;

        return Integer.compare(x,o.x);
    }

    @Override
    public String toString() {
        return "Pair{" +
                "value=" + value +
                ", y=" + y +
                ", x=" + x +
                '}';
    }
}
public class Lol {
    static long[][] d = new long[1010][1010];
    static int M = 1000000007;
    static long[] rivit = new long[1010];
    static long[] kolumnit = new long[1010];


    public static void main(String[] args) throws IOException {
        //createTestData();
        //System.exit(0);

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("lol.txt")));
        int n = Integer.parseInt(reader.readLine());
        long time = System.currentTimeMillis();
        ArrayList<Pair> pairs = new ArrayList<>(n*n);
        for (int y = 0; y < n; y++) {
            String[] rivi = reader.readLine().split(" ");
            for (int x = 0; x < rivi.length; x++) {
                int val = Integer.parseInt(rivi[x]);
                pairs.add(new Pair(val,y,x));
            }
        }
        Collections.sort(pairs);
        int curnumber = pairs.get(0).value;
        ArrayList<Pair> toedit = new ArrayList<>();
        //System.out.println(pairs);
        long sum = 0;
        for (Pair pair : pairs) {

            int y = pair.y;
            int x = pair.x;
            int value = pair.value;
            if (value != curnumber) {
                for (Pair p : toedit) {
                    rivit[p.y] += d[p.y][p.x];
                    rivit[p.y] %= M;
                    kolumnit[p.x] += d[p.y][p.x];
                    kolumnit[p.x] %= M;
                }
                toedit.clear();
                curnumber = value;
            }
            d[y][x] += rivit[y] + kolumnit[x] + 1;
            d[y][x] %= M;
            //System.out.println(rivit[y] + " " + kolumnit[x] + " " + d[y][x]);

            sum += d[y][x];
            sum %= M;
            toedit.add(pair);
        }
        System.out.println(sum);
        //System.out.println(System.currentTimeMillis()-time);
    }

    private static void createTestData() throws IOException {
        FileWriter writer = new FileWriter("lol.txt");
        Random random = new Random();
        int n = 1000;
        StringBuilder builder = new StringBuilder();
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                builder.append(random.nextInt(999)+1).append(" ");
            }
            builder.append("\n");
        }
        writer.write(builder.substring(0,builder.length()-1));
        writer.close();
    }
}

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: TIME LIMIT EXCEEDED