Submission #223437

#	Time	Username	Problem	Language	Result	Execution time	Memory
223437		MrDomino	Rectangles (IOI19_rect)	C++14	72 / 100	5095 ms	380080 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 stv[N];
int top;

struct KEKMAN
{
    int x;
    int l;
    int r;
};

bool operator < (KEKMAN a, KEKMAN b)
{
    if (a.x != b.x)
    {
        return a.x < b.x;
    }
    else
    {
        return a.r < b.r;
    }
}

bool operator == (KEKMAN a, KEKMAN b)
{
    return (a.x == b.x && a.r == b.r);
}

vector<KEKMAN> rows;
vector<KEKMAN> cols;

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

struct T
{
    int a;
    int b;
    int c;
    int d;
};

bool operator < (T f, T s)
{
    if (f.a != s.a) return f.a < s.a;
    if (f.b != s.b) return f.b < s.b;
    if (f.c != s.c) return f.c < s.c;
    return f.d < s.d;
}

bool operator != (T f, T s)
{
    if (f.a != s.a) return 1;
    if (f.b != s.b) return 1;
    if (f.c != s.c) return 1;
    if (f.d != s.d) return 1;
    return 0;
}

vector<T> solutions;



void check(int r1, int c1, int r2, int c2)
{
    if (!good(r1, c1) || !good(r2, c2))
    {
        return;
    }
    if (r1 > r2 || c1 > c2)
    {
        return;
    }
    for (int r = r1; r <= r2; r++)
    {
        if (dr[r][c1] != c2 && st[r][c2] != c1)
        {
            return;
        }
    }
    for (int c = c1; c <= c2; c++)
    {
        if (jos[r1][c] != r2 && sus[r2][c] != r1)
        {
            return;
        }
    }
    solutions.push_back({r1, c1, r2, c2});
}

int lx[N][N];
int rx[N][N];
int ly[N][N];
int ry[N][N];

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;
        stv[0] = 0;
        for (int j = 1; j <= m; j++)
        {
            while (top && a[i][stv[top]] < a[i][j])
            {
                top--;
            }
            st[i][j - 1] = stv[top] + 1;
            stv[++top] = j;
        }
        top = 0;
        stv[0] = m + 1;
        for (int j = m; j >= 1; j--)
        {
            while (top && a[i][stv[top]] < a[i][j])
            {
                top--;
            }
            dr[i][j + 1] = stv[top] - 1;
            stv[++top] = j;
        }
    }
    for (int j = 1; j <= m; j++)
    {
        top = 0;
        stv[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            while (top && a[stv[top]][j] < a[i][j])
            {
                top--;
            }
            sus[i - 1][j] = stv[top] + 1;
            stv[++top] = i;
        }
        top = 0;
        stv[0] = n + 1;
        for (int i = n; i >= 1; i--)
        {
            while (top && a[stv[top]][j] < a[i][j])
            {
                top--;
            }
            jos[i + 1][j] = stv[top] - 1;
            stv[++top] = i;
        }
    }
    for (int i = 2; i < n; i++)
    {
        for (int j = 2; j < m; j++)
        {
            if (1 < st[i][j] && st[i][j] <= j)
            {
                rows.push_back({i, st[i][j], j});
            }
            if (dr[i][j] < m && j <= dr[i][j])
            {
                rows.push_back({i, j, dr[i][j]});
            }
            if (1 < sus[i][j] && sus[i][j] <= i)
            {
                cols.push_back({j, sus[i][j], i});
            }
            if (jos[i][j] < n && i <= jos[i][j])
            {
                cols.push_back({j, i, jos[i][j]});
            }
        }
    }
    sort(rows.begin(), rows.end());
    sort(cols.begin(), cols.end());
    int pos = 0;
    for (int r2 = 1; r2 <= n; r2++)
    {
        for (int c2 = 1; c2 <= m; c2++)
        {
            KEKMAN it = {r2, 0, c2};
            while (pos < (int) rows.size() && rows[pos] < it)
            {
                pos++;
            }
            if (pos < (int) rows.size() && rows[pos] == it)
            {
                int i = pos, j;
                while (pos + 1 < (int) rows.size() && rows[pos + 1] == it)
                {
                    pos++;
                }
                j = pos;
                lx[r2][c2] = i;
                rx[r2][c2] = j;
                pos++;
            }
            else
            {
                lx[r2][c2] = -1;
                rx[r2][c2] = -1;
            }
        }
    }
    pos = 0;
    for (int c2 = 1; c2 <= m; c2++)
    {
        for (int r2 = 1; r2 <= n; r2++)
        {
            KEKMAN it = {c2, 0, r2};
            while (pos < (int) cols.size() && cols[pos] < it)
            {
                pos++;
            }
            if (pos < (int) cols.size() && cols[pos] == it)
            {
                int i = pos, j;
                while (pos + 1 < (int) cols.size() && cols[pos + 1] == it)
                {
                    pos++;
                }
                j = pos;
                ly[r2][c2] = i;
                ry[r2][c2] = j;
                pos++;
            }
            else
            {
                ly[r2][c2] = -1;
                ry[r2][c2] = -1;
            }
        }
    }
    for (int r = 1; r <= n; r++)
    {
        for (int c = 1; c <= m; c++)
        {
            if (lx[r][c] != -1 && ly[r][c] != -1)
            {
                for (int i = lx[r][c]; i <= rx[r][c]; i++)
                {
                    int c1 = rows[i].l;
                    for (int j = ly[r][c]; j <= ry[r][c]; j++)
                    {
                        int r1 = cols[j].l;
                        check(r1, c1, r, c);
                    }
                }
            }
        }
    }
    if (solutions.empty())
    {
        return 0;
    }
    sort(solutions.begin(), solutions.end());
    int sol = 1;
    for (int i = 1; i < (int) solutions.size(); i++)
    {
        sol += (solutions[i] != solutions[i - 1]);
    }
    return sol;
}

• 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