Ruudukko

#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#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) ^ get<1>(x) ^ get<2>(x);
    }
};

int get_line_row(int y, int v)
{
    if (v == line_row_last[y])
    {
        return line_row[y];
    }
    line_row_last[y] = v;
    int s;
    s = (line_row[y] + line_row_added[y]) % DIVISOR;
    line_row_added[y] = 0;
    line_row[y] = s;

    return s;
}
int get_line_col(int x, int v)
{
    if (v == line_col_last[x])
    {
        return line_col[x];
    }
    line_col_last[x] = v;
    int s;
    s = (line_col[x] + line_col_added[x]) % DIVISOR;
    line_col_added[x] = 0;
    line_col[x] = s;

    return s;
}

int calculate_routes(int number, int x, int y)
{
    int value;
    // if (number == 1)
    // {
    //     value = 1;
    // }
    // else
    // {
    value = (get_line_col(x, number) + get_line_row(y, number) + 1) % DIVISOR;
    // }
    total += value;
    total %= DIVISOR;
    line_row_added[y] += value;
    line_row_added[y] %= DIVISOR;
    line_col_added[x] += value;
    line_col_added[x] %= DIVISOR;
    return value;
}
bool cmp(tuple<int, int, int> x, tuple<int, int, int> y)
{
    return get<0>(x) > get<0>(y);
}

int main()
{
    int n;
    cin >> n;
    // vector<int> grid;
    // grid.reserve(n * n);
    unordered_set<tuple<int, int, int>, hashFunction> values_coords;
    values_coords.reserve(n * n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int a;
            cin >> a;
            // grid.push_back(a);
            values_coords.insert(make_tuple(a, j, i));
        }
    }

    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(v.begin(), v.end(), cmp);

    // set<tuple<int, int, int>> order(values_coords.begin(), values_coords.end());
    vector<tuple<int, int, int>>::iterator itr;
    for (itr = v.begin(); itr != v.end(); itr++)
    {
        calculate_routes(get<0>(*itr), get<1>(*itr), get<2>(*itr));
    }
    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: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED