Ruudukko

#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
using namespace std;
 
const int DIVISOR = 1000000007;
 
vector<int> line_row(1000);
vector<int> line_row_last(1000);
vector<int> line_col(1000);
vector<int> line_col_last(1000);
vector<int> line_row_added(1000);
vector<int> line_col_added(1000);
set<tuple<int, int, int>> values_coords;
int total = 0;
 
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 y, int x, int number)
{
    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;
}
 
class Node
{
    // "Binary Search Tree node"
public:
    vector<tuple<int, int>> values;
    Node *parent;
    Node *left;
    Node *right;
    int key;
    int marker = 0;
    bool is_root;
    bool has_left = false;
    bool has_right = false;
    int var_pos;
 
    Node(int key_)
    {
        key = key_;
        is_root = true;
    }
 
    Node(Node &parent_, int key_)
    {
        key = key_;
        parent = &parent_;
        marker = 0;
    }
 
    Node *next()
    {
        if (marker == 0)
        {
            marker += 1;
            if (has_left)
            {
                return left;
            }
        }
        if (marker == 1)
        {
            marker += 1;
            if (has_right)
            {
                return right;
            }
        }
        marker = 0;
        return parent;
    }
    void routes_calc()
    {
        for (auto v : values)
        {
            calculate_routes(key, get<1>(v), get<0>(v));
        }
    }
};
 
class BST
{
    Node *root;
    BST(int middle)
    {
        Node node = Node(middle);
        root = &node;
    }
    void Insert(int key, tuple<int, int> value)
    {
 
        Node *node = search(key);
        if (node->var_pos == 1)
        {
            Node nod = Node(*node, key);
            node->left = &nod;
            node->left->values.push_back(value);
            node->has_left = true;
        }
        else if (node->var_pos == 2)
        {
            Node nod = Node(*node, key);
            node->right = &nod;
            node->right->values.push_back(value);
            node->has_right = true;
        }
        else
        {
            node->values.push_back(value);
        }
    }
 
    void Iter()
    {
        Node *node = root;
        Node *neue;
        while (true)
        {
            neue = node->next();
            if (node == root and node->marker == 0)
            {
                break;
            }
            if (node->marker == 0)
            {
                // # neue is parent
                if (neue->marker == 1)
                {
                    // node is left
                    neue->routes_calc();
                }
            }
            else if (neue->has_left == false)
            {
                neue->routes_calc();
            }
            node = neue;
        }
    }
 
    Node *search(int key_)
    {
        // """returns a node and a number.
        // 0 means the node has the wanted value,
        // 1 means the value doesn't exist but would be the node's left branch if inserted,
        // 2 means the same as 1 but for the right branch."""
        // # no recursion
        Node *current = root;
        while (true)
        {
            if (key_ < current->key)
            {
                if (current->has_left)
                {
                    current = current->left;
                }
                else
                {
                    current->var_pos = 1;
                    return current;
                }
            }
            else if (key_ > current->key)
            {
                if (current->has_right)
                {
                    current = current->right;
                }
                else
                {
                    current->var_pos = 2;
                    return current;
                }
            }
            else
            {
                current->var_pos = 0;
                return current;
            }
        }
    }
};
 
int main()
{
    int n;
    cin >> n;
    vector<vector<int>> grid;
    // grid.reserve(n * n);
    for (int i = 0; i < n; i++)
    {
        vector<int> b;
        for (int j = 0; j < n; j++)
        {
            int a;
            cin >> a;
            b.push_back(a);
        }
        grid.push_back(b);
    }
 
    vector<int> line_row(n, 0);
    vector<int> line_row_last(n, 1);
    vector<int> line_col(n, 0);
    vector<int> line_col_last(n, 1);
    vector<int> line_row_added(n, 0);
    vector<int> line_col_added(n, 0);
 
    // vector<unordered_set<int>> exists_row;
    // set<int> exists_all;
    for (int y = 0; y < n; y++)
    {
        // unordered_set<int> s;
        for (int x = 0; x < n; x++)
        {
            // s.insert(grid[y][x]);
            // exists_all.insert(grid[y][x]);
            values_coords.insert(make_tuple(grid[y][x], x, y));
        }
        // exists_row.push_back(s);
    }
    set<tuple<int, int, int>>::iterator itr;
    for (itr = values_coords.begin(); itr != values_coords.end(); itr++)
    {
        calculate_routes(get<2>(*itr), get<1>(*itr), get<0>(*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: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED