Submission #222957

#	Time	Username	Problem	Language	Result	Execution time	Memory
222957		MrDomino	Rectangles (IOI19_rect)	C++14	50 / 100	5084 ms	613968 KiB

rect

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

using namespace std;

typedef long long ll;

const int N = 2500 + 7;
int v[N];
int stk[N];
int top;
int l[N];
int r[N];

vector<pair<int, int>> potential(vector<int> b)
{
    int n = (int) b.size();
    for (int i = 1; i <= n;i ++)
    {
        v[i] = b[i - 1];
    }
    top = 0;
    stk[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        while (top && v[stk[top]] < v[i])
        {
            top--;
        }
        l[i] = stk[top];
        stk[++top] = i;
    }
    top = 0;
    stk[0] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        while (top && v[stk[top]] < v[i])
        {
            top--;
        }
        r[i] = stk[top];
        stk[++top] = i;
    }
    vector<pair<int, int>> sol;
    for (int i = 1; i <= n; i++)
    {
        int j = l[i];
        if (1 <= j && i - j >= 2)
        {
            sol.push_back({j, i});
        }
        j = r[i];
        if (j <= n && j - i >= 2)
        {
            sol.push_back({i, j});
        }
    }
    for (auto &it : sol)
    {
        it.first--;
        it.second--;
        it.first++;
        it.second--;
    }
    if (sol.empty())
    {
        return sol;
    }
    sort(sol.begin(), sol.end());
    vector<pair<int, int>> sol2;
    sol2.push_back(sol[0]);
    for (int i = 1; i < (int) sol.size(); i++)
    {
        if (sol[i] != sol[i - 1])
        {
            sol2.push_back(sol[i]);
        }
    }
    return sol2;
}


vector<vector<pair<int, int>>> pot_row;
vector<vector<pair<int, int>>> pot_col;
vector<vector<set<int>>> inv;

bool has(int c, int r1, int r2)
{
    return inv[r1][r2].count(c);
}

long long count_rectangles(vector<vector<int>> a)
{
    int n = (int) a.size();
    int m = (int) a[0].size();
    pot_row.resize(n);
    pot_col.resize(m);
    for (int i = 0; i < n; i++)
    {
        pot_row[i] = potential(a[i]);
    }
    for (int j = 0; j < m; j++)
    {
        vector<int> b;
        for (int i = 0; i < n; i++)
        {
            b.push_back(a[i][j]);
        }
        pot_col[j] = potential(b);
    }
    vector<vector<vector<int>>> who_row(m);
    inv.resize(n);
    for (int i = 0; i < n; i++)
    {
        inv[i].resize(n);
    }
    for (int c = 0; c < m; c++)
    {
        for (auto &it : pot_col[c])
        {
            int r1 = it.first;
            int r2 = it.second;
            inv[r1][r2].insert(c);
        }
    }
    for (int i = 0; i < m; i++)
    {
        who_row[i].resize(m, {});
    }
    for (int i = 0; i < n; i++)
    {
        for (auto &it : pot_row[i])
        {
            int c1 = it.first;
            int c2 = it.second;
            who_row[c1][c2].push_back(i);
        }
    }
    inv.resize(n);
    ll sol = 0;
    for (int c1 = 0; c1 < m; c1++)
    {
        for (int c2 = c1; c2 < m; c2++)
        {
            vector<int> rows = who_row[c1][c2];
            set<int> goods;

            if (rows.empty())
            {
                continue;
            }
            int i = 0;
            while (i < (int) rows.size())
            {
                int j = i;
                while (j + 1 < (int) rows.size() && rows[j + 1] == rows[j] + 1)
                {
                    j++;
                }
                for (int k = i; k <= j; k++)
                {
                    for (int k2 = k; k2 <= j; k2++)
                    {
                        int r1 = rows[k];
                        int r2 = rows[k2];
                        bool good = 1;
                        for (int c = c1; c <= c2; c++)
                        {
                            if (has(c, r1, r2) == 0)
                            {
                                good = 0;
                                break;
                            }
                        }
                        if (good)
                        {
                            sol++;
                        }
                    }
                }
                i = j + 1;
            }
        }
    }
    return sol;
}

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