Ruudukko

#include <iostream>
#include <chrono>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

class GridCell{
public:
    int x;
    int y;
    int value;
    GridCell(){
        this->x = -1;
        this->y = -1;
        this->value = -1;
    };
    GridCell(int x, int y, int value){
        this->x = x;
        this->y = y;
        this->value = value;
    }
};
bool compare(GridCell A, GridCell B){
    return A.value > B.value;
}

int binarySearchLastIndex(GridCell* arr, int left, int right, int &key)
{
    int mid = (right + left) / 2;
    if (arr[mid].value == key){
        while(arr[mid + 1].value == key){
            mid++;
        }
        return mid;
    }
    else if (arr[mid].value < key) {
        return binarySearchLastIndex(arr, left, mid - 1, key);
    }
    else {
        return binarySearchLastIndex(arr, mid + 1, right, key);
    }

    return -1;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // INPUT
    int gridSize;
    cin >> gridSize;
    //int grid[gridSize * gridSize];
    int gridCounter[gridSize * gridSize];
    vector<GridCell> gridValues(gridSize * gridSize);
    vector<GridCell*> sortedRows = vector<GridCell*>(gridSize);
    vector<GridCell*> sortedCols = vector<GridCell*>(gridSize);
    for (int i = 0; i < gridSize; i++){
        sortedRows[i] = new GridCell[gridSize];
        sortedCols[i] = new GridCell[gridSize];
    }
    for (int y = 0; y < gridSize; y++){
        for (int x = 0; x < gridSize; x++){
            int val;
            cin >> val;
            //grid[(y * gridSize) + x] = val;
            gridCounter[(y * gridSize) + x] = 1;
            gridValues[(y * gridSize) + x] = GridCell(x, y, val);
            sortedRows[y][x] = GridCell(x, y, val);
            sortedCols[x][y] = GridCell(x, y, val);
        }
    }
    sort(gridValues.begin(), gridValues.end(), compare);
    for (int i = 0; i < gridSize; i++){
        sort(sortedRows[i], sortedRows[i] + gridSize, compare);
        sort(sortedCols[i], sortedCols[i] + gridSize, compare);
    }
    
    /*int gridSize = 1000;
    int* grid = new int[gridSize * gridSize];
    int* gridCounter = new int[gridSize * gridSize];
    vector<GridCell> gridValues(gridSize * gridSize);
    vector<GridCell*> sortedRows = vector<GridCell*>(gridSize);
    vector<GridCell*> sortedCols = vector<GridCell*>(gridSize);
    for (int i = 0; i < gridSize; i++){
        sortedRows[i] = new GridCell[gridSize];
        sortedCols[i] = new GridCell[gridSize];
    }
    for (int y = 0; y < gridSize; y++){
        for (int x = 0; x < gridSize; x++){
            grid[(y * gridSize) + x] = (x+1) * (y+1);
            gridCounter[(y * gridSize) + x] = 1;
            gridValues[(y * gridSize) + x] = GridCell(x, y, grid[(y * gridSize) + x]);
            sortedRows[y][x] = GridCell(x, y, grid[(y * gridSize) + x]);
            sortedCols[x][y] = GridCell(x, y, grid[(y * gridSize) + x]);
        }
    }
    sort(gridValues.begin(), gridValues.end(), compare);
    for (int i = 0; i < gridSize; i++){
        sort(sortedRows[i], sortedRows[i] + gridSize, compare);
        sort(sortedCols[i], sortedCols[i] + gridSize, compare);
    }*/


    //auto start = std::chrono::high_resolution_clock::now();
    
    // ALG
    unsigned long long int totalCount = 0;
    for (int i = 0; i < gridSize * gridSize; i++){
        GridCell c = gridValues[i];
        int thisCellValue = c.value;
        int thisCellCounter = gridCounter[(c.y * gridSize) + c.x];

        int lastIndexY = binarySearchLastIndex(sortedCols[c.x], 0, gridSize, thisCellValue);
        GridCell* endG = sortedCols[c.x] + gridSize;
        for (GridCell* ptrG = sortedCols[c.x] + lastIndexY + 1; ptrG != endG; ptrG++){
            gridCounter[(ptrG->y * gridSize) + ptrG->x] = (gridCounter[(ptrG->y * gridSize) + ptrG->x] + thisCellCounter) % 1000000007;
        }

        int lastIndexX = binarySearchLastIndex(sortedRows[c.y], 0, gridSize, thisCellValue);
        endG = sortedRows[c.y] + gridSize;
        for (GridCell* ptrG = sortedRows[c.y] + lastIndexX + 1; ptrG != endG; ptrG++){
            gridCounter[(ptrG->y * gridSize) + ptrG->x] = (gridCounter[(ptrG->y * gridSize) + ptrG->x] + thisCellCounter) % 1000000007;
        }

        totalCount = (totalCount + thisCellCounter) %  1000000007;
    }


    //auto end = std::chrono::high_resolution_clock::now();
    //cout << "TIME: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() / 1000.0 << "\n"; 
    
    cout << totalCount;
}
    


// 80 332 806
// 223 600 547  <-- +1s

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: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED