Ruudukko

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int N =1e5;
const int inf = 1e9;
const ll mod = 1e9 + 7;
 
 
 
int main(){
 
 
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int> (n));
    vector<pair<int, pair<int, int>>> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j]; 
            m.push_back({a[i][j], {i, j}});
        }
    }
    sort(m.begin(), m.end());
    vector<vector<ll>> ans(n, vector<ll> (n));
    vector<ll> cols(n), rows(n);
    ll sum = 0;
    int pre = 1, prei = 0;
    for(int i = 0; i < n * n; ++i){
 
 
        auto [val, p] = m[i];
 
        if(val != pre){
            pre = val;
            for(int j = prei; j < i; ++j){
                auto [val2, p2] = m[j];
                int y = p2.first, x = p2.second;
                sum+=ans[y][x];
                sum%=mod;
                cols[x]+=ans[y][x];
                cols[x]%=mod;
                rows[y]+=ans[y][x];
                rows[y]%=mod;
            }
            prei = i;
        }
 
        int y = p.first, x = p.second;
        ans[y][x] = 1;
 
        ans[y][x] += cols[x];
        ans[y][x] %= mod;        
        
        ans[y][x] += rows[y];
        ans[y][x] %= mod;
    }    
    for(int i = prei; i < n * n; ++i){
        auto [val, p] = m[i];
        int y = p.first, x = p.second;
        sum+=ans[y][x];
        sum%=mod;
    }
 
 
    cout << sum << "\n";
 
 
 
    
}

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