Submission #570828

#	Time	Username	Problem	Language	Result	Execution time	Memory
570828		Stickfish	Rectangles (IOI19_rect)	C++17	72 / 100	5038 ms	170188 KiB

rect

#include "rect.h"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;

const int INF = 1e9 + 177013;

struct cell {
    short l;
    short r;
    short u;
    short d;

    cell operator+(cell a) {
        cell ans;
        ans.l = min(l, a.l);
        ans.u = min(u, a.u);
        ans.r = max(r, a.r);
        ans.d = max(d, a.d);
        return ans;
    }
};

vector<vector<cell>> cl;

ll solve_01(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
    vector<int> height(m, n + 123);
    vector<int> wall(m, 0);
    for (int i = n - 1; i >= n - 2; --i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 0) {
                ++height[j];
                wall[j] = 0;
            } else {
                ++wall[j];
                height[j] = 0;
            }
        }
    }
    ll ans = 0;
    for (int i = n - 3; i >= 0; --i) {
        int pv0 = -123;
        for (int j = 0; j < m; ++j) {
            if (height[j] == 0) {
                if (pv0 != -123 && pv0 != j - 1) {
                    bool isok = min(wall[j], wall[pv0]) >= height[pv0 + 1];
                    for (int k = pv0 + 1; k < j && isok; ++k) {
                        if (k > pv0 + 1)
                            isok &= height[k] == height[k - 1];
                        isok &= a[i][k] == 1;
                    }
                    if (isok) {
                        cerr << i << ' ' << pv0 << ' ' << j << endl;
                        ++ans;
                    }
                }
                pv0 = j;
            }
        }
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 0) {
                ++height[j];
                wall[j] = 0;
            } else {
                ++wall[j];
                height[j] = 0;
            }
        }
    }
    return ans;
}

ll count_rectangles(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
    bool all_01 = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            all_01 &= a[i][j] < 2;
        }
    }
    if (all_01 && n >= 3 && m >= 3)
        return solve_01(a);
    cl.assign(n, vector<cell>(m));
    for (int i = 0; i < n; ++i) {
        vector<pair<int, int>> stck = {{INF, -1}};
        for (int j = 0; j < m; ++j) {
            while (stck.back().first <= a[i][j])
                stck.pop_back();
            cl[i][j].l = stck.back().second;
            stck.push_back({a[i][j], j});
        }
    }
    for (int i = 0; i < n; ++i) {
        vector<pair<int, int>> stck = {{INF, m}};
        for (int j = m - 1; j >= 0; --j) {
            while (stck.back().first <= a[i][j])
                stck.pop_back();
            cl[i][j].r = stck.back().second;
            stck.push_back({a[i][j], j});
        }
    }
    for (int j = 0; j < m; ++j) {
        vector<pair<int, int>> stck = {{INF, -1}};
        for (int i = 0; i < n; ++i) {
            while (stck.back().first <= a[i][j])
                stck.pop_back();
            cl[i][j].u = stck.back().second;
            stck.push_back({a[i][j], i});
        }
    }
    for (int j = 0; j < m; ++j) {
        vector<pair<int, int>> stck = {{INF, n}};
        for (int i = n - 1; i >= 0; --i) {
            while (stck.back().first <= a[i][j])
                stck.pop_back();
            cl[i][j].d = stck.back().second;
            stck.push_back({a[i][j], i});
        }
    }
    vector<vector<cell>> colmn(n, vector<cell>(m));
    ll ans = 0;
    for (int i = n - 2; i > 0; --i) {
        for (int j = m - 2; j > 0; --j) {
            colmn[i][j] = cl[i][j];
            for (int u = i; u < n - 1; ++u) {
                cell board = cl[i][j];
                for (int v = j; v < m - 1; ++v) {
                    if (u > i)
                        colmn[u][v] = colmn[u][v] + cl[i][v];
                    board = board + colmn[u][v];
                    if (board.u < i - 1 || board.l < j - 1 || board.d > u + 1)
                        break;
                    if (board.r <= v + 1) {
                        ++ans;
                    }
                }
            }
        }
    }
	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