Submission #223352

#	Time	Username	Problem	Language	Result	Execution time	Memory
223352		MrDomino	Rectangles (IOI19_rect)	C++14	50 / 100	5066 ms	484532 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;

bool has_row(int r, pair<int, int> it)
{
    int lo = 0, hi = (int) pot_row[r].size() - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (pot_row[r][mid] == it)
        {
            return 1;
        }
        if (pot_row[r][mid] < it)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return 0;
}

bool has_col(int c, pair<int, int> it)
{
    int lo = 0, hi = (int) pot_col[c].size() - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (pot_col[c][mid] == it)
        {
            return 1;
        }
        if (pot_col[c][mid] < it)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return 0;
}

bool check(int r1, int c1, int r2, int c2)
{
    for (int r = r1; r <= r2; r++)
    {
        if (has_row(r, {c1, c2}) == 0)
        {
            return 0;
        }
    }
    for (int c = c1; c <= c2; c++)
    {
        if (has_col(c, {r1, r2}) == 0)
        {
            return 0;
        }
    }
    return 1;
}

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);
    vector<vector<vector<int>>> rows(n);
    vector<vector<vector<int>>> cols(n);
    for (int i = 0; i < n; i++)
    {
        rows[i].resize(m);
        cols[i].resize(m);
    }
    for (int i = 0; i < n; i++)
    {
        pot_row[i] = potential(a[i]);
        for (auto &it : pot_row[i])
        {
            cols[i][it.second].push_back(it.first);
        }
    }
    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);
        for (auto &it : pot_col[j])
        {
            rows[it.second][j].push_back(it.first);
        }
    }
    ll sol = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (auto &r : rows[i][j])
            {
                for (auto &c : cols[i][j])
                {
                    if (check(r, c, i, j))
                    {
                        sol++;
                    }
                }
            }
        }
    }
    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