Submission #222943

#	Time	Username	Problem	Language	Result	Execution time	Memory
222943		MrDomino	Rectangles (IOI19_rect)	C++14	0 / 100	150 ms	147708 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--;
    }
    sort(sol.begin(), sol.end());
    return sol;
}

void print(vector<pair<int, int>> a)
{
    for (auto &it : a)
    {
        cout << " : " << it.first << " " << it.second << "\n";
    }
}

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

bool has(int c, int r1, int r2)
{
    pair<int, int> it = {r1, r2};
    int lo = 0;
    int 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;
}

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);
    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);
        }
    }
    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;
    for (int c1 = 0; c1 < m; c1++)
    {
        for (int c2 = c1; c2 < m; c2++)
        {
            cout << "on " << c1 << " and " << c2 << " : ";
            for (auto &i : who_row[c1][c2])
            {
                cout << i << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
    return 0;
}

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