Ruudukko

#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <map>
#include <utility>
#include <bits/stdc++.h>
using namespace std;
 
const int DIVISOR = 1000000007;
vector<int> line_row;
vector<int> line_row_last;
vector<int> line_col;
vector<int> line_col_last;
vector<int> line_row_added;
vector<int> line_col_added;
int total = 0;
struct hashFunction
{
    size_t operator()(const tuple<int, int, int> &x) const
    {
        return get<0>(x);
    }
};
 
inline void calculate_routes(int number, int x, int y)
{
    if (number != line_col_last[x])
    {
        line_col_last[x] = number;
        line_col[x] = (line_col[x] + line_col_added[x]) % DIVISOR;
        line_col_added[x] = 0;
    }
    if (number != line_row_last[y])
    {
        line_row_last[y] = number;
        line_row[y] = (line_row[y] + line_row_added[y]) % DIVISOR;
        line_row_added[y] = 0;
    }
 
    int value = (line_col[x] + line_row[y] + 1) % DIVISOR;
    total = (total + value) % DIVISOR;
    line_row_added[y] = (line_row_added[y] + value) % DIVISOR;
    line_col_added[x] = (line_col_added[x] + value) % DIVISOR;
}
bool cmp(const pair<int, pair<int, int>> &x, const pair<int, pair<int, int>> &y)
{
    return x.first < y.first;
}
 
int main()
{
    int n;
    cin >> n;
    // unordered_set<tuple<int, int, int>, hashFunction> values_coords;
    // values_coords.reserve(n * n);
    vector<pair<int, pair<int, int>>> values_coords_vec;
    values_coords_vec.reserve(n * n);
    int i, j, a;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            cin >> a;
            values_coords_vec.push_back(pair<int, pair<int, int>>(a, pair<int, int>(j, i)));
        }
    }
    // multimap<int, pair<int, int>> values_coords(values_coords_vec.begin(), values_coords_vec.end());
 
    line_row = vector<int>(n, 0);
    line_row_last = vector<int>(n, 1);
    line_col = vector<int>(n, 0);
    line_col_last = vector<int>(n, 1);
    line_row_added = vector<int>(n, 0);
    line_col_added = vector<int>(n, 0);
 
    // vector<tuple<int, int, int>> v(values_coords.begin(), values_coords.end());
    sort(values_coords_vec.begin(), values_coords_vec.end(), cmp);
 
    vector<pair<int, pair<int, int>>>::iterator itr;
    for (itr = values_coords_vec.begin(); itr != values_coords_vec.end(); itr++)
    {
        calculate_routes(itr->first, itr->second.first, itr->second.second);
    }
    cout << total << "\n";
 
    return 0;
}

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