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>>();
map<int, ll> counts;
map<int, pair<int,ll>> rowSum;
map<int, ll> lastRowSum;
 
void countPaths(pair<int,int> x) {
	auto r = rowSum[x.second / n + 1];
	auto c = rowSum[-( x.second % n) - 1];
	
	
	if (r.first < x.first) {
		counts[x.second] += r.second;
		if (!lastRowSum.count(x.second / n +1))
			lastRowSum[x.second / n + 1] = 0;
		else 
			lastRowSum[x.second / n + 1] = r.second;
	} else {
		counts[x.second] += lastRowSum[x.second / n + 1];
		rowSum[x.second / n + 1].second += lastRowSum[x.second / n +1];
	}
	
	if (c.first < x.first) {
		counts[x.second] += c.second;
		
		if (!lastRowSum.count(- (x.second % n) - 1))
			lastRowSum[ - (x.second % n) - 1] = 0;
		else 
			lastRowSum[- (x.second % n) - 1] = c.second;

	} else {
		counts[x.second] += lastRowSum[-(x.second%n)-1];
		rowSum[- (x.second%n) - 1].second += lastRowSum[-(x.second%n)-1];
	}
	
	rowSum[x.second / n + 1] = {x.first, counts[x.second] + r.second};
	rowSum[-(x.second % n) - 1] = {x.first, counts[x.second] + c.second};
	
	 counts[x.second] %= 1000000007;
	 rowSum[x.second/n + 1].second %= 1000000007;
	 rowSum[-(x.second%n)-1].second %= 1000000007;
	 lastRowSum[x.second/n + 1] %= 1000000007;
	 lastRowSum[-(x.second%n)-1] %= 1000000007;
}
 
 
int main() {
    cin >> n;
 
    for (int i=1; i<n+1; i++) {
        rowSum[i] = {0,0};
        rowSum[-i] = {0,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});
            counts[n*i+j] = 1;
        }
    }
    for (auto it = allNumbers.begin(); it != allNumbers.end(); it++) {
        countPaths(*it);
    }
    ll total = 0;
    for (auto x : counts) {
        total += x.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: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED