Submission #725289

#	Time	Username	Problem	Language	Result	Execution time	Memory
725289		t6twotwo	Rectangles (IOI19_rect)	C++17	10 / 100	8 ms	572 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> F(vector<int> A) {
    int N = A.size();
    vector<int> B(N), stk{-1};
    for (int i = 0; i < N; i++) {
        while (stk.back() != -1 && (A[stk.back()] < A[i])) {
            stk.pop_back();
        }
        B[i] = stk.back();
        stk.push_back(i);
    }
    return B;
}
vector<int> R(vector<int> A) {
    int N = A.size();
    vector<int> B(N);
    for (int i = 0; i < N; i++) {
        if (A[i] == -1) {
            B[N - 1 - i] = -1;
        } else {
            B[N - 1 - i] = N - 1 - A[i];
        }
    }
    return B;
}
long long count_rectangles(vector<vector<int>> A) {
    int N = A.size();
    int M = A[0].size();
    int ans = 0, D1 = 0, D2 = 0;
    for (int mask = 0; mask < 4; mask++) {
        vector A2(N, vector<int>(M));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                A2[mask % 2 == 0 ? i : N - 1 - i][mask / 2 % 2 == 0 ? j : M - 1 - j] = A[i][j];
            }
        }
        swap(A, A2);
        vector<vector<int>> X(N), XR(N);
        for (int i = 0; i < N; i++) {
            X[i] = R(F(vector(A[i].rbegin(), A[i].rend())));
            XR[i] = F(A[i]);
        }
        vector Y(N, vector<int>(M));
        vector YR(N, vector<int>(M));
        for (int j = 0; j < M; j++) {
            vector<int> B(N);
            for (int i = 0; i < N; i++) {
                B[i] = A[i][j];
            }
            auto C = R(F(vector(B.rbegin(), B.rend())));
            auto D = F(B);
            for (int i = 0; i < N; i++) {
                Y[i][j] = C[i];
                YR[i][j] = D[i];
            }
        }
        for (int j = 1; j < M - 1; j++) {
            for (int i = 1; i < N - 1; i++) {
                if (X[i][j - 1] == -1 || X[i][j - 1] == j) {
                    continue;
                }
                int k = i;
                while (k < N - 1 && (X[k][j - 1] == X[i][j - 1] || XR[k][X[i][j - 1]] == j - 1)) {
                    k++;
                }
                for (int x = i; x < k; x++) {
                    if (X[x][j - 1] != X[i][j - 1] || Y[x - 1][j] == -1 || Y[x - 1][j] > k || Y[x - 1][j] == x) {
                        continue;
                    }
                    bool ok = 1;
                    for (int y = j; y < X[i][j - 1]; y++) {
                        if (!(Y[x - 1][y] == Y[x - 1][j] || YR[Y[x - 1][j]][y] == x - 1)) {
                            ok = 0;
                        }
                    }
                    if (ok) {
                        ans++;
                        bool u = A[x][j - 1] == A[x][X[x][j - 1]];
                        bool v = A[x - 1][j] == A[Y[x - 1][j]][j];
                        if (u && v) {
                            D2++;
                        } else if (u || v) {
                            D1++;
                        }
                    }
                }
            }
        }
        swap(A, A2);
    }
    ans -= D1;
    ans -= 3 * D2;
    return ans;
}

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