Submission #725290

#	Time	Username	Problem	Language	Result	Execution time	Memory
725290		t6twotwo	Rectangles (IOI19_rect)	C++17	23 / 100	2388 ms	177788 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 || Y[i - 1][j] == -1 || Y[i - 1][j] == i) {
                    continue;
                }
                bool ok = 1;
                int i2 = Y[i - 1][j];
                int j2 = X[i][j - 1];
                for (int x = i; x < i2; x++) {
                    for (int y = j; y < j2; y++) {
                        if (A[x][y] >= min({A[x][j - 1], A[x][j2], A[i - 1][y], A[i2][y]})) {
                            ok = 0;
                        }
                    }
                }
                if (ok) {
                    ans++;
                    bool u = A[i][j - 1] == A[i][j2];
                    bool v = A[i - 1][j] == A[i2][j];
                    if (u && v) {
                        D2++;
                    } else if (u || v) {
                        D1++;
                    }
                }
            }
        }
        swap(A, A2);
    }
    ans -= D1 / 2;
    ans -= D2 / 4 * 3;
    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