Submission #837422

#	Time	Username	Problem	Language	Result	Execution time	Memory
837422		finn__	Rectangles (IOI19_rect)	C++17	72 / 100	3032 ms	1048580 KiB

rect

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

using namespace std;
using L = long long;

template <typename T, int64_t N>
struct FenwickTree
{
    T t[N];

    void update(int64_t i, T x)
    {
        ++i;
        while (i <= N)
            t[i - 1] += x, i += i & -i;
    }

    T prefix_sum(int64_t i)
    {
        T x = 0;
        ++i;
        while (i)
            x += t[i - 1], i -= i & -i;
        return x;
    }
};

constexpr size_t N = 2504;

vector<uint16_t> h[N][N], v[N][N];
vector<pair<uint16_t, uint16_t>> h_[N][N], v_[N][N];
FenwickTree<int32_t, N> tree;

L count_rectangles(vector<vector<int>> a)
{
    size_t const n = a.size(), m = a[0].size();
    for (size_t i = 0; i < n; ++i)
    {
        stack<size_t> s;
        for (size_t j = 0; j < m; ++j)
        {
            while (!s.empty() && a[i][s.top()] < a[i][j])
                s.pop();
            if (!s.empty() && j - s.top() >= 2)
                h[s.top()][j].push_back(i);
            if (!s.empty() && a[i][s.top()] == a[i][j])
                s.pop();
            s.push(j);
        }

        while (!s.empty())
            s.pop();

        for (size_t j = m - 1; j < m; --j)
        {
            while (!s.empty() && a[i][s.top()] < a[i][j])
                s.pop();
            if (!s.empty() && s.top() - j >= 2 && a[i][s.top()] != a[i][j])
                h[j][s.top()].push_back(i);
            if (!s.empty() && a[i][s.top()] == a[i][j])
                s.pop();
            s.push(j);
        }
    }
    for (size_t j = 0; j < m; ++j)
    {
        stack<size_t> s;
        for (size_t i = 0; i < n; ++i)
        {
            while (!s.empty() && a[s.top()][j] < a[i][j])
                s.pop();
            if (!s.empty() && i - s.top() >= 2)
                v[s.top()][i].push_back(j);
            if (!s.empty() && a[s.top()][j] == a[i][j])
                s.pop();
            s.push(i);
        }

        while (!s.empty())
            s.pop();

        for (size_t i = n - 1; i < n; --i)
        {
            while (!s.empty() && a[s.top()][j] < a[i][j])
                s.pop();
            if (!s.empty() && s.top() - i >= 2 && a[s.top()][j] != a[i][j])
                v[i][s.top()].push_back(j);
            if (!s.empty() && a[s.top()][j] == a[i][j])
                s.pop();
            s.push(i);
        }
    }

    a = vector<vector<int>>();

    for (size_t i = 0; i < m; ++i)
        for (size_t j = i + 2; j < m; ++j)
            for (size_t k = 0; k < h[i][j].size();)
            {
                size_t l = k + 1;
                while (l < h[i][j].size() && h[i][j][l] == h[i][j][l - 1] + 1)
                    ++l;
                for (size_t p = k; p < l; ++p)
                    if (h[i][j][p])
                        h_[h[i][j][p] - 1][i].emplace_back(j, h[i][j][l - 1] + 1);
                k = l;
            }

    for (auto &x : h)
        for (auto &y : x)
            y = vector<uint16_t>();

    for (size_t i = 0; i < n; ++i)
        for (size_t j = i + 2; j < n; ++j)
            for (size_t k = 0; k < v[i][j].size();)
            {
                size_t l = k + 1;
                while (l < v[i][j].size() && v[i][j][l] == v[i][j][l - 1] + 1)
                    ++l;
                for (size_t p = k; p < l; ++p)
                    if (v[i][j][p])
                        v_[i][v[i][j][p] - 1].emplace_back(j, v[i][j][l - 1] + 1);
                k = l;
            }

    for (auto &x : v)
        for (auto &y : x)
            y = vector<uint16_t>();

    L ans = 0;
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
        {
            sort(v_[i][j].begin(), v_[i][j].end(), [](auto const &a, auto const &b)
                 { return a.second > b.second; });
            sort(h_[i][j].begin(), h_[i][j].end(), [](auto const &a, auto const &b)
                 { return a.first > b.first; });
            auto it = v_[i][j].begin();
            for (auto jt = h_[i][j].begin(); jt != h_[i][j].end(); ++jt)
            {
                while (it != v_[i][j].end() && it->second >= jt->first)
                {
                    tree.update(it->first, 1);
                    ++it;
                }
                L x = tree.prefix_sum(jt->second);
                ans += x;
            }

            for (auto jt = v_[i][j].begin(); jt != it; ++jt)
                tree.update(jt->first, -1);
            v_[i][j] = vector<pair<uint16_t, uint16_t>>();
        }

    return ans;
}

• 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