제출 #655832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655832		Richem	Rectangles (IOI19_rect)	C++14	100 / 100	4615 ms	687840 KiB

rect

#include "rect.h"
#include <iostream>
#include <stack>
#include <map>
using namespace std;

const int MAX_TAILLE = 2542, INF = 1e9;

int nbLigne, nbCol;
int grille[MAX_TAILLE][MAX_TAILLE];

void input() {
    cin >> nbLigne >> nbCol;

    for(int lig = 0; lig < nbLigne; lig++) {
        for(int col = 0; col < nbCol; col++) {
            cin >> grille[lig][col];
        }
    }
}

int segment[MAX_TAILLE][MAX_TAILLE][2][2];
int valide[MAX_TAILLE][MAX_TAILLE] = {0};

void algo1d(int direction, int pos) {
    int limitePos2 = nbCol;
    if(direction % 2 == 1)
        limitePos2 = nbLigne;

    stack<pair<int, int>> grandAvant;
    grandAvant.push({-INF, INF});

    for(int pos2 = 0; pos2 < limitePos2; pos2++) {
        int vraiPos2 = pos2;

        if(direction >= 2)
            vraiPos2 = limitePos2 - 1 - pos2;

        int valCur = grille[pos][vraiPos2];

        if(direction % 2 == 1)
            valCur = grille[vraiPos2][pos];

        while(grandAvant.top().second <= valCur)
            grandAvant.pop();

        int extremite = grandAvant.top().first+1;

        if(direction >= 2)
            extremite -= 2;

        //cout <<vraiPos2 << " " << pos << " " << extremite << " " << valCur<< endl;

        if(direction % 2 == 0)
            segment[pos][vraiPos2][0][direction/2] = extremite;
        else
            segment[vraiPos2][pos][1][direction/2] = extremite;
        grandAvant.push({vraiPos2, valCur});
    }
}

pair<int, int> prolonge[MAX_TAILLE][MAX_TAILLE];
void resetProlonge() {
    for(int deb = 0; deb < MAX_TAILLE; deb++) {
        for(int fin = 0; fin < MAX_TAILLE; fin++) {
            prolonge[deb][fin] = {-1, 1};
        }
    }
}

int delta[2] = {-1, 1};

void balaieHorizontal(int direction) {
    resetProlonge();

    for(int lig = 0; lig < nbLigne; lig++) {
        for(int col = 0; col < nbCol; col++) {
            int posLig = lig;
            if(direction == 1)
                posLig = nbLigne - 1 - lig;

            int debSeg = segment[posLig][col][0][0];
            int finSeg = segment[posLig][col][0][1];

            if(debSeg < 0 || finSeg < 0 || segment[posLig][col][1][0] < 0 || segment[posLig][col][1][1] < 0)
                continue;

            if(prolonge[debSeg][finSeg].first == posLig + delta[direction])
                prolonge[debSeg][finSeg].second++;
            else if(prolonge[debSeg][finSeg].first * delta[direction] > (posLig + delta[direction]) * delta[direction])
                prolonge[debSeg][finSeg].second = 1;
            prolonge[debSeg][finSeg].first = posLig;

            //cout << posLig << " " << col << " " << debSeg << " " << finSeg << " " << prolonge[debSeg][finSeg].second << " " << segment[posLig][col][1][direction] << endl;

            if(abs(segment[posLig][col][1][direction] - posLig) + 1 <= prolonge[debSeg][finSeg].second) {
                valide[posLig][col]++;
            }
        }
    }
}

void balaieVertical(int direction) {
    resetProlonge();

    for(int col = 0; col < nbCol; col++) {
        for(int lig = 0; lig < nbLigne; lig++) {
            int posCol = col;

            if(direction == 1)
                posCol = nbCol - col - 1;

            int debSeg = segment[lig][posCol][1][0];
            int finSeg = segment[lig][posCol][1][1];

            if(debSeg < 0 || finSeg < 0 || segment[lig][posCol][0][0] < 0 || segment[lig][posCol][0][1] < 0)
                continue;

            if(prolonge[debSeg][finSeg].first == posCol + delta[direction])
                prolonge[debSeg][finSeg].second++;
            else if(prolonge[debSeg][finSeg].first * delta[direction] > (posCol + delta[direction]) * delta[direction])
                prolonge[debSeg][finSeg].second = 1;
            prolonge[debSeg][finSeg].first = posCol;

            if(abs(segment[lig][posCol][0][direction] - posCol) + 1 <= prolonge[debSeg][finSeg].second) {
                valide[lig][posCol]++;
            }
        }
    }
}

int total = 0;

map<pair<pair<int, int>, pair<int, int>>, int> qui;

long long count_rectangles(std::vector<std::vector<int> > a) {
    nbLigne = a.size();
    nbCol = a[0].size();

    for(int lig = 0; lig < nbLigne; lig++) {
        for(int col = 0; col < nbCol; col++) {
            grille[lig][col] = a[lig][col];
        }
    }

    for(int lig = 0; lig < nbLigne; lig++) {
        algo1d(0, lig);
        algo1d(2, lig);
    }
    for(int col = 0; col < nbCol; col++) {
        algo1d(1, col);
        algo1d(3, col);
    }

    /*
    for(int lig = 0; lig < nbLigne; lig++) {
        for(int col = 0; col < nbCol; col++) {
            cout << lig << " " << col << " " << segment[lig][col][0][0] << " " << segment[lig][col][0][1] << endl;
        }
    }

    for(int lig = 0; lig < nbLigne; lig++) {
        for(int col = 0; col < nbCol; col++) {
            cout << lig << " " << col << " " << segment[lig][col][1][0] << " " << segment[lig][col][1][1] << endl;
        }
    }
    */

    balaieHorizontal(0);
    balaieHorizontal(1);
    balaieVertical(0);
    balaieVertical(1);

    for(int lig = 0; lig < nbLigne; lig++) {
        for(int col = 0; col < nbCol; col++) {
            int gauche = segment[lig][col][0][0], droite = segment[lig][col][0][1];
            int haut = segment[lig][col][1][0], bas = segment[lig][col][1][1];
            //cout << lig << " " << col << " " << valide[lig][col] << endl;
            if(valide[lig][col] == 4 && qui[{{gauche, droite}, {haut, bas}}] == 0) {
                total++;
                qui[{{gauche, droite}, {haut, bas}}] = 1;
            }
        }
    }
	return total;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28