Submission #837029

#	Time	Username	Problem	Language	Result	Execution time	Memory
837029		finn__	Rectangles (IOI19_rect)	C++17	49 / 100	4848 ms	53756 KiB

rect

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse4")

#include <bits/stdc++.h>

#include "rect.h"

using namespace std;
using L = long long;

constexpr size_t N = 700;

int16_t p[N][N], q[N][N], r[N][N], s[N][N];
bitset<N> rowwise[N], colwise[N], mask[N];

L count_rectangles(vector<vector<int>> a)
{
    int16_t const n = a.size(), m = a[0].size();
    for (int16_t i = 0; i < n; ++i)
        for (int16_t j = 0; j < m; ++j)
        {
            p[i][j] = j + 1;
            q[i][j] = j - 1;
            r[i][j] = i + 1;
            s[i][j] = i - 1;
            while (p[i][j] < m && a[i][p[i][j]] < a[i][j])
                ++p[i][j];
            while (q[i][j] >= 0 && a[i][q[i][j]] < a[i][j])
                --q[i][j];
            while (r[i][j] < n && a[r[i][j]][j] < a[i][j])
                ++r[i][j];
            while (s[i][j] >= 0 && a[s[i][j]][j] < a[i][j])
                --s[i][j];
        }

    vector<pair<int16_t, int16_t>> left_end, top_end;
    for (int16_t i = 1; i + 1 < n; ++i)
        for (int16_t j = 2; j < m; ++j)
            left_end.emplace_back(i, j);
    for (int16_t i = 2; i < n; ++i)
        for (int16_t j = 1; j + 1 < m; ++j)
            top_end.emplace_back(i, j);
    sort(left_end.begin(), left_end.end(), [](auto const &a, auto const &b)
         { return q[a.first][a.second] < q[b.first][b.second]; });
    sort(top_end.begin(), top_end.end(), [](auto const &a, auto const &b)
         { return s[a.first][a.second] < s[b.first][b.second]; });

    for (int16_t i = 0; i < N; ++i)
        for (int16_t j = 0; j <= i; ++j)
            mask[i][j] = 1;

    L ans = 0;
    auto it = top_end.begin();

    for (int16_t i = 0; i + 2 < n; ++i)
    {
        while (it < top_end.end() && s[it->first][it->second] <= i)
            colwise[it->first][it->second] = 1, ++it;

        for (bitset<N> &b : rowwise)
            b.reset();
        auto jt = left_end.begin();

        for (int16_t j = 0; j + 2 < m; ++j)
        {
            while (jt < left_end.end() && q[jt->first][jt->second] <= j)
                rowwise[jt->first][jt->second] = 1, ++jt;

            vector<int16_t> top_limitation;
            for (int16_t k = m - 1; k > j; --k)
            {
                while (!top_limitation.empty() && r[i][k] <= r[i][top_limitation.back()])
                    top_limitation.pop_back();
                top_limitation.push_back(k);
            }
            reverse(top_limitation.begin(), top_limitation.end());

            bitset<N> possible;
            for (int16_t k = j + 2; k < m; ++k)
                possible[k] = 1;
            int16_t col_upper_lim = m - 1;
            for (int16_t k = i + 1; k + 1 < n; ++k)
            {
                col_upper_lim = min(col_upper_lim, p[k][j]);
                possible &= rowwise[k];
                if (!top_limitation.empty() && k >= r[i][top_limitation.back()])
                {
                    col_upper_lim = min(col_upper_lim, top_limitation.back());
                    top_limitation.pop_back();
                }

                ans += (possible & mask[min<size_t>(col_upper_lim, (~colwise[k + 1])._Find_next(j))]).count();
            }
        }
    }

    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'L count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int16_t' {aka 'short int'} and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   48 |     for (int16_t i = 0; i < N; ++i)
      |                         ~~^~~

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