Submission #570184

#	Time	Username	Problem	Language	Result	Execution time	Memory
570184		Stickfish	Rectangles (IOI19_rect)	C++17	59 / 100	5063 ms	67652 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 count_rectangles(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
    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});
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            assert(cl[i][j].u == -1 || a[cl[i][j].u][j] > a[i][j]);
            assert(cl[i][j].l == -1 || a[i][cl[i][j].l] > a[i][j]);
            assert(cl[i][j].d == n || a[cl[i][j].d][j] > a[i][j]);
            assert(cl[i][j].r == m || a[i][cl[i][j].r] > a[i][j]);
        }
    }
    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: 0 / 13
• Subtask 7: 0 / 28