Ruudukko

#include <iostream>
#include <map>
#include <set>
#include <vector>
 
using namespace std;
 
using ll = long long;
 
int n;
set<pair<int,int>> allNumbers = set<pair<int,int>>();
vector<ll> counts;
vector<pair<int,ll>> rowSum;
vector<ll> lastRowSum;
vector<bool> v;
 
void countPaths(pair<int,int> x) {
	int r_num = n + x.second / n ;
	int c_num = (x.second % n);
	auto r = rowSum[r_num];
	auto c = rowSum[c_num];
	
	
	if (r.first < x.first) {
		counts[x.second] += r.second;
		if (!v[r_num]) {
			lastRowSum[r_num] = 0;
			v[r_num] = 1;
		}
		else 
			lastRowSum[r_num] = r.second;
	} else {
		counts[x.second] += lastRowSum[r_num];
		rowSum[r_num].second += lastRowSum[r_num];
	}
	
	if (c.first < x.first) {
		counts[x.second] += c.second;
		
		if (!v[c_num]) {
			lastRowSum[c_num] = 0;
			v[c_num] = 1;
		}
		else 
			lastRowSum[c_num] = c.second;
 
	} else {
		counts[x.second] += lastRowSum[c_num];
		rowSum[c_num].second += lastRowSum[c_num];
	}
	
	rowSum[r_num] = {x.first, counts[x.second] + r.second};
	rowSum[c_num] = {x.first, counts[x.second] + c.second};
	
	 counts[x.second] %= 1000000007;
	 rowSum[r_num].second %= 1000000007;
	 rowSum[c_num].second %= 1000000007;
	 lastRowSum[r_num] %= 1000000007;
	 lastRowSum[c_num] %= 1000000007;
}
 
 
int main() {
    cin >> n;
    counts = vector<ll>(n*n,1);
    rowSum = vector<pair<int,ll>>(2*n, {0,0});
    lastRowSum = vector<ll>(2*n,0);
    v = vector<bool>(2*n,0);
    int k;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> k;
            allNumbers.insert({k, n*i+j});
        }
    }
    ll total = 0;
    for (auto it = allNumbers.begin(); it != allNumbers.end(); it++) {
        countPaths(*it);
        total += counts[(*it).second];
    }
    total %= 1000000007;
 
    cout << total;
}

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