Ruudukko

input/code.cpp: In function 'int main()':
input/code.cpp:142:18: warning: unused variable 't' [-Wunused-variable]
  142 |         __int128 t = (rr + rr1 + 1) % AAAA;
      |                  ^

#include <bits/stdc++.h>

using namespace std;

const __int128 AAAA = 1000000007;

__int128 reitit[1000][1000];
__int128 ruudukko[1000][1000];
pair<int, pair<int, int>> rows[1000][1000];
pair<int, pair<int, int>> cols[1000][1000];
__int128 reititcols[1000][1000];
__int128 reititrows[1000][1000];
int colsij[1000][1000];
int rowsij[1000][1000];
__int128 aacols[1000];
__int128 aarows[1000];
__int128 oacols[1000];
__int128 oarows[1000];
int ec[1000];
int er[1000];

__int128 maaralaske_reitit = 0;
__int128 maaralaske_reitit_nopea = 0;

bool rowcolcmp(pair<int, pair<int, int>> i, pair<int, pair<int, int>> j)
{
    return i.first < j.first;
}

int main()
{
    int n;
    priority_queue<pair<int, pair<int, int>>> q;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int arvo;
            //cin >> ruudukko[i][j];
            cin >> arvo;
            ruudukko[j][i] = arvo;
            q.push(make_pair(-arvo, make_pair(j, i)));
            rows[i][j] = make_pair(arvo, make_pair(j, i)); // :/
            cols[j][i] = make_pair(arvo, make_pair(j, i)); // ** :/ **

            reitit[i][j] = -1;
        }
        aacols[i] = 0;
        aarows[i] = 0;
        oacols[i] = 0;
        oarows[i] = 0;
        ec[i] = 0x7fffffff;
        er[i] = 0x7fffffff;
    }

    for (int i = 0; i < n; i++) {
        sort(rows[i], rows[i]+n, rowcolcmp);
        sort(cols[i], cols[i]+n, rowcolcmp);

        for (int j = 0; j < n; j++) {
            pair<int, int> a = cols[i][j].second;
            pair<int, int> b = rows[i][j].second;

            colsij[a.first][a.second] = j;
            rowsij[b.first][b.second] = j;
        }
    }

    /*for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            //cout << rows[i][j].first << endl;
            cout << i << ", " << j << ": " << colsij[i][j] << endl;
        }
    }*/

    //cout << "BEGIN --------------\n";

    __int128 nreitit = 0;

    while (!q.empty()) {
        pair<int, pair<int, int>> a = q.top();
        int i = a.second.first;
        int j = a.second.second;
        int b = -a.first;
        q.pop();
        //cout << "------------- " << i << ", " << j << ":  " << b << endl;

        if (ec[i] != b) {
            aacols[i] += oacols[i];
            oacols[i] = 0;
        }

        if (er[j] != b) {
            aarows[j] += oarows[j];
            oarows[j] = 0;
        }

        int acol = colsij[i][j] - 1;
        int edellinen = -1;
        __int128 rr = 0;
        __int128 rc = aacols[i];
        for (int k = acol; k >= 0; k--) {
            pair<int, pair<int, int>> d = cols[i][k];
            int c = d.first;

            if (c == b) {
                continue;
            }
            
            if (edellinen != -1 && c < edellinen) {
                break;
            }

            edellinen = c;
            rr = (rr + reitit[d.second.first][d.second.second]) % AAAA;
        }

        int arow = rowsij[i][j] - 1;
        edellinen = -1;
        __int128 rr1 = 0;
        __int128 rw = aarows[j];
        for (int k = arow; k >= 0; k--) {
            pair<int, pair<int, int>> d = rows[j][k];
            int c = d.first;

            if (c == b) {
                continue;
            }
            
            if (edellinen != -1 && c < edellinen) {
                break;
            }

            edellinen = c;
            rr1 = (rr1 + reitit[d.second.first][d.second.second]) % AAAA;
            //cout << "- " << d.second.first << ", " << d.second.second << endl;
            //cout << k << " " << rr1 << " " << rw << endl;
        }

        //cout << "rrrr: " << (long long) rr << " " << (long long) rc << " " << (long long) rr1 << " " << (long long) rw << endl;

        //__int128 t = (rr + rr1 + rw + rc) % AAAA;
        __int128 t = (rr + rr1 + 1) % AAAA;
        //cout << "--" << endl;
        //cout << (int64_t) t << endl;
        //cout << (int64_t) (t + rw + rc) << endl;
        oacols[i] = (oacols[i] + rw + rc + 1) % AAAA;
        oarows[j] = (oarows[j] + rw + rc + 1) % AAAA;
        er[j] = b;
        ec[i] = b;
        //reititrows[j][i] = t;
        //reititcols[i][j] = t;
        //reititrows[j][i] = rr1;
        //reititcols[i][j] = rr;
        //reititrows[j][i] = (rr1 + rw) % AAAA;
        //reititcols[i][j] = (rr + rc) % AAAA;
        reitit[i][j] = (rw + rc + 1) % AAAA;
        nreitit += (rw + rc + 1) % AAAA;
    }

    nreitit %= AAAA;
    cout << (int64_t) nreitit << endl;
    //cout << "Määrä laske_reitit: " << maaralaske_reitit << endl;
    //cout << "Määrä laske_reitit nopea: " << maaralaske_reitit_nopea << endl;
}

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