Submission #223372

#	Time	Username	Problem	Language	Result	Execution time	Memory
223372		MrDomino	Rectangles (IOI19_rect)	C++14	37 / 100	5062 ms	83704 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;

const int N = 2500 + 7;
int n;
int m;
int a[N][N];
int st[N][N];
int dr[N][N];
int sus[N][N];
int jos[N][N];
int stk[N];
int top;

bool good(int r, int c)
{
    return (1 < r && 1 < c && r < n && c < m);
}

bool check(int r1, int c1, int r2, int c2)
{
    if (!good(r1, c1) || !good(r2, c2))
    {
        return 0;
    }
    for (int r = r1; r <= r2; r++)
    {
        if (dr[r][c1] != c2 && st[r][c2] != c1)
        {
            return 0;
        }
    }
    for (int c = c1; c <= c2; c++)
    {
        if (jos[r1][c] != r2 && sus[r2][c] != r1)
        {
            return 0;
        }
    }
    return 1;
}

long long count_rectangles(vector<vector<int>> b)
{
    n = (int) b.size();
    m = (int) b[0].size();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = b[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        top = 0;
        stk[0] = 0;
        for (int j = 1; j <= m; j++)
        {
            while (top && a[i][stk[top]] < a[i][j])
            {
                top--;
            }
            st[i][j - 1] = stk[top] + 1;
            stk[++top] = j;
        }
        top = 0;
        stk[0] = m + 1;
        for (int j = m; j >= 1; j--)
        {
            while (top && a[i][stk[top]] < a[i][j])
            {
                top--;
            }
            dr[i][j + 1] = stk[top] - 1;
            stk[++top] = j;
        }
    }
    for (int j = 1; j <= m; j++)
    {
        top = 0;
        stk[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            while (top && a[stk[top]][j] < a[i][j])
            {
                top--;
            }
            sus[i - 1][j] = stk[top] + 1;
            stk[++top] = i;
        }
        top = 0;
        stk[0] = n + 1;
        for (int i = n; i >= 1; i--)
        {
            while (top && a[stk[top]][j] < a[i][j])
            {
                top--;
            }
            jos[i + 1][j] = stk[top] - 1;
            stk[++top] = i;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int i2 = i; i2 <= n; i2++)
            {
                for (int j2 = j; j2 <= m; j2++)
                {
                    if (check(i, j, i2, j2))
                    {
                        ans++;
                    }
                }
            }
        }
    }
    return ans;
}

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