Submission #1202437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202437		LucaIlie	Rectangles (IOI19_rect)	C++20	23 / 100	3620 ms	269948 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2500;
const int INF = 1e9;
int n, m;
long long ans = 0;
int mat[MAX_N + 2][MAX_N + 2];
int leftG[MAX_N + 2][MAX_N + 2], leftGE[MAX_N + 2][MAX_N + 2];
int rightG[MAX_N + 2][MAX_N + 2], rightGE[MAX_N + 2][MAX_N + 2];
int upG[MAX_N + 2][MAX_N + 2], upGE[MAX_N + 2][MAX_N + 2];
int downG[MAX_N + 2][MAX_N + 2], downGE[MAX_N + 2][MAX_N + 2];
vector<int> st;

void init();

void solve(bool eqL, bool eqC) {
//    printf("%d %d\n", eqL, eqC);

    init();

    /*
    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m; c++) 
            printf("%d ", leftGE[l][c]);
        printf("\n");
    }
    printf("\n");

    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m; c++) 
            printf("%d ", rightGE[l][c]);
        printf("\n");
    }
    printf("\n");

    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m; c++) 
            printf("%d ", mat[l][c]);
        printf("\n");
    }
    printf("\n");

    */

    for (int l1 = 1; l1 <= n; l1++) {
        for (int c1 = 1; c1 <= m; c1++) {
            int c2 = rightGE[l1 + 1][c1], l2 = downGE[l1][c1 + 1];

            if (l2 > n || c2 > m || l2 - l1 <= 1 || c2 - c1 <= 1)
                continue;

            if (mat[l1 + 1][c1] == mat[l1 + 1][c2] && eqC)
                continue;
            if (mat[l1][c1 + 1] == mat[l2][c1 + 1] && eqL)
                continue;


            bool ok = true;
            for (int l = l1 + 1; l <= l2 - 1; l++) 
                ok &= (rightGE[l][c1] == c2 || (leftGE[l][c2] == c1));
            for (int c = c1 + 1; c <= c2 - 1; c++) 
                ok &= (downGE[l1][c] == l2 || (upGE[l2][c] == l1));

            int afl1 = l1, afl2 = l2, afc1 = c1, afc2 = c2;
            if (eqL)
                afl1 = n + 1 - l2, afl2 = n + 1 - l1;
            if (eqC)
                afc1 = m + 1 - c2, afc2 = m + 1 - c1;

            /*
            if (ok)
                printf("%d %d %d %d\n", afl1, afc1, afl2, afc2);
            if (ok)
                printf("%d %d %d %d\n\n", l1, c1, l2, c2);
            */

            ans += ok;
        }
    }
    //printf("\n\n");
}

void rotVert() {
    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m / 2; c++) {
            swap(mat[l][c], mat[l][m + 1 - c]);

            swap(upG[l][c], upG[l][m + 1 - c]);
            swap(upGE[l][c], upGE[l][m + 1 - c]);
            swap(downGE[l][c], downGE[l][m + 1 - c]);
            swap(downG[l][c], downG[l][m + 1 - c]);

            swap(leftG[l][c], rightG[l][m + 1 - c]);
            swap(leftGE[l][c], rightGE[l][m + 1 - c]);
            swap(rightG[l][c], leftG[l][m + 1 - c]);
            swap(rightGE[l][c], leftGE[l][m + 1 - c]);

            leftG[l][c] = m + 1 - leftG[l][c];
            leftGE[l][c] = m + 1 - leftGE[l][c];
            rightG[l][c] = m + 1 - rightG[l][c];
            rightGE[l][c] = m + 1 - rightGE[l][c];
        }
    }
}

void rotHoriz() {
    for (int l = 1; l <= n / 2; l++) {
        for (int c = 1; c <= m; c++) {
            swap(mat[l][c], mat[n + 1 - l][c]);

            swap(leftG[l][c], leftG[n + 1 - l][c]);
            swap(leftGE[l][c], leftGE[n + 1 - l][c]);
            swap(rightG[l][c], rightG[n + 1 - l][c]);
            swap(rightGE[l][c], rightGE[n + 1 - l][c]);

            swap(upG[l][c], downG[n + 1 - l][c]);
            swap(upGE[l][c], downGE[n + 1 - l][c]);
            swap(downG[l][c], upG[n + 1 - l][c]);
            swap(downGE[l][c], upGE[n + 1 - l][c]);

            upG[l][c] = n + 1 - upG[l][c];
            upGE[l][c] = n + 1 - upGE[l][c];
            downG[l][c] = n + 1 - downG[l][c];
            downGE[l][c] = n + 1 - downGE[l][c];
        }
    }
}

void init() {
    for (int l = 1; l <= n; l++) {
        mat[l][0] = INF;
        st.clear();
        st.push_back(0);
        for (int c = 1; c <= m; c++) {
            while (mat[l][c] > mat[l][st.back()]) 
                st.pop_back();
            leftGE[l][c] = st.back();
            st.push_back(c);
        }
        st.clear();
        st.push_back(0);
        for (int c = 1; c <= m; c++) {
            while (mat[l][c] >= mat[l][st.back()]) 
                st.pop_back();
            leftG[l][c] = st.back();
            st.push_back(c);
        }

        mat[l][m + 1] = INF;
        st.clear();
        st.push_back(m + 1);
        for (int c = m; c >= 1; c--) {
            while (mat[l][c] > mat[l][st.back()]) 
                st.pop_back();
            rightGE[l][c] = st.back();
            st.push_back(c);
        }
        st.clear();
        st.push_back(m + 1);
        for (int c = m; c >= 1; c--) {
            while (mat[l][c] >= mat[l][st.back()]) 
                st.pop_back();
            rightG[l][c] = st.back();
            st.push_back(c);
        }
    }

    for (int c = 1; c <= m; c++) {
        mat[0][c] = INF;
        st.clear();
        st.push_back(0);
        for (int l = 1; l <= n; l++) {
            while (mat[l][c] > mat[st.back()][c])
                st.pop_back();
            upGE[l][c] = st.back();
            st.push_back(l);
        }
        st.clear();
        st.push_back(0);
        for (int l = 1; l <= n; l++) {
            while (mat[l][c] >= mat[st.back()][c])
                st.pop_back();
            upG[l][c] = st.back();
            st.push_back(l);
        }
        
        mat[n + 1][c] = INF;
        st.clear();
        st.push_back(n + 1);
        for (int l = n; l >= 1; l--) {
            while (mat[l][c] > mat[st.back()][c])
                st.pop_back();
            downGE[l][c] = st.back();
            st.push_back(l);
        }
        st.clear();
        st.push_back(n + 1);
        for (int l = n; l >= 1; l--) {
            while (mat[l][c] >= mat[st.back()][c])
                st.pop_back();
            downG[l][c] = st.back();
            st.push_back(l);
        }
    }

 
}
long long count_rectangles(vector<vector<int>> a) {
    n = a.size(), m = a[0].size();

    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m; c++) 
            mat[l][c] = a[l - 1][c - 1];
    }

    init();
   /*
    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m; c++)
            printf("%d ", leftG[l][c]);
        printf("\n");
    }
    */

    /*
    for (int l = 1; l <= n; l++) {
        for (int c = 1; c <= m; c++)
            printf("%d ", downGE[l][c]);
        printf("\n");
    }
    */

    for (int a = 0; a < 2; a++) {
        for (int b = 0; b < 2; b++) {
            solve(a, b);
            rotVert();
        }
        rotHoriz();
    }

    return ans;
}

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