Submission #766869

#	Time	Username	Problem	Language	Result	Execution time	Memory
766869		t6twotwo	Rectangles (IOI19_rect)	C++17	72 / 100	5083 ms	537704 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
    int L, R, U, D;
    T() {
        L = U = -1;
        R = D = 2500;
    }
    T(int x, int y, int z, int t) {
        L = x;
        R = y;
        U = z;
        D = t;
    }
};
T F(T &a, T &b) {
    return {max(a.L, b.L), min(a.R, b.R), max(a.U, b.U), min(a.D, b.D)};
}
vector<int> ms(vector<int> &a, bool f) {
    int n = a.size();
    vector<int> b(n, f ? n : -1), stk;
    for (int i = (f ? n - 1 : 0); i != (f ? -1 : n); i += (f ? -1 : 1)) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            b[i] = stk.back();
        }
        stk.push_back(i);
    }
    return b;
}
ll count_rectangles(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
    bool subtask6 = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] > 1) {
                subtask6 = 0;
            }
        }
    }
    int ans = 0;
    if (subtask6) {
        vector pfs(n, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                pfs[i][j + 1] = pfs[i][j] + a[i][j];
            }
        }
        vector<int> Q(n);
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                Q[i] = a[i][j] == 0 ? Q[i] + 1 : 0;
            }
            if (j == 0 || j == m - 1) {
                continue;
            }
            for (int i = 1, k = 1; i < n - 1; i = k) {
                while (k < n - 1 && (Q[i] == Q[k] && a[i][j + 1] == a[k][j + 1])) {
                    k++;
                }
                if (Q[i] > 0 && a[i][j + 1] == 1 && j - Q[i] >= 0 && pfs[i - 1][j + 1] - pfs[i - 1][j - Q[i] + 1] == Q[i] && pfs[k][j + 1] - pfs[k][j - Q[i] + 1] == Q[i]) {
                    ans++;
                }
            }
        }
        return ans;
    }
    vector S(n, vector<T>(m));
    for (int i = 0; i < n; i++) {
        auto l = ms(a[i], 0);
        auto r = ms(a[i], 1);
        for (int j = 0; j < m; j++) {
            S[i][j].L = l[j];
            S[i][j].R = r[j];
        }
    }
    for (int j = 0; j < m; j++) {
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = a[i][j];
        }
        auto u = ms(v, 0);
        auto d = ms(v, 1);
        for (int i = 0; i < n; i++) {
            S[i][j].U = u[i];
            S[i][j].D = d[i];
        }
    }
    auto check = [&](int x1, int y1, int x2, int y2) -> int {
        if (x1 > x2 || y1 > y2 || x1 < 1 || y1 < 1 || x2 >= n - 1 || y2 >= m - 1) {
            return 0;
        }
        for (int i = y1; i <= y2; i++) {
            if (S[x1 - 1][i].D <= x2 || S[x2 + 1][i].U >= x1) {
                return 0;
            }
        }
        for (int i = x1; i <= x2; i++) {
            if (S[i][y1 - 1].R <= y2 || S[i][y2 + 1].L >= y1) {
                return 0;
            }
        }
        return 1;
    };
    vector Q(n, vector<vector<int>>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (S[i][j].U != -1) {
                Q[S[i][j].U][j].push_back(i);
            }
        }
    }
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            int y = S[i][j - 1].R - 1;
            if (y != m - 1) {
                int x = S[i - 1][j].D - 1;
                if (x != n - 1) {
                    ans += check(i, j, x, y);
                }
                for (int k : Q[i - 1][j]) {
                    if (a[i - 1][j] != a[k][j]) {
                        ans += check(i, j, k - 1, y);
                    }
                }
            }
            y = S[i][j + 1].L + 1;
            if (y != 0 && a[i][j + 1] != a[i][y - 1]) {
                int x = S[i - 1][j].D - 1;
                if (x != n - 1) {
                    ans += check(i, y, x, j);
                }
                for (int k : Q[i - 1][j]) {
                    if (a[i - 1][j] != a[k][j]) {
                        ans += check(i, y, k - 1, j);
                    }
                }
            }
        }
    }
    return ans;
}

• 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: 0 / 28