Submission #474969

#	Time	Username	Problem	Language	Result	Execution time	Memory
474969		Lam_lai_cuoc_doi	Rectangles (IOI19_rect)	C++17	100 / 100	4133 ms	965092 KiB

rect

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2.5e3 + 5;

struct FenwickTree
{
    ll a[N];
    int n;
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, ll v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    ll Get(int p)
    {
        ll ans(0);
        for (; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }
} f;

#define fi first
#define se second

int m, n;
vector<pair<int, int>> bycol[N][N], byrow[N][N];
vector<int> tmp[N][N];
int l[N], r[N];

void Prepare(const vector<vector<int>> &a, const int &m, const int &n, vector<pair<int, int>> by[N][N], bool rotated)
{
    for (int i = 0; i < m; ++i)
    {
        vector<int> s;
        s.reserve(n);

        for (int j = 0; j < n; ++j)
        {
            while (!s.empty() && a[i][s.back()] <= a[i][j])
                s.pop_back();
            l[j] = s.empty() ? -1 : s.back();
            s.emplace_back(j);
        }

        s.clear();

        for (int j = n - 1; ~j; --j)
        {
            while (!s.empty() && a[i][s.back()] <= a[i][j])
                s.pop_back();
            r[j] = s.empty() ? n : s.back();
            s.emplace_back(j);
        }

        for (int j = 0; j < n; ++j)
            tmp[l[j] + 1][r[j] - 1].emplace_back(i);
    }

    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
        {
            for (int u = 0, v = 1; u < (int)tmp[i][j].size(); ++u)
            {
                v = u + 1;
                while (v < (int)tmp[i][j].size() && tmp[i][j][v] - tmp[i][j][v - 1] <= 1)
                    ++v;
                //cerr << i << " " << j << " " << tmp[i][j][u] << " " << tmp[i][j][v - 1] << " is:\n";

                for (int z = tmp[i][j][u]; z <= tmp[i][j][v - 1]; ++z)
                {

                    int x1 = z, x2 = i;
                    int y1 = j, y2 = min(tmp[i][j][v - 1], m - 2);

                    if (rotated)
                    {
                        swap(x1, x2);
                        swap(y1, y2);
                    }

                    by[x1][x2].emplace_back(y1, y2);
                    //cerr << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
                }

                u = v - 1;
            }
            tmp[i][j].clear();
        }
}

bool com(const pair<int, int> &x, const pair<int, int> &y)
{
    return x.second > y.second || (x.second == y.second && x.first < y.first);
}

ll count_rectangles(vector<vector<int>> a)
{
    m = a.size();
    n = a[0].size();
    f.n = n;

    vector<vector<int>> b(n, vector<int>(m));

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            b[j][i] = a[i][j];

    Prepare(a, m, n, byrow, 0);
    Prepare(b, n, m, bycol, 1);

    ll ans(0);
    /*for (int i = 1; i < m - 1; ++i)
        for (int j = 1; j < n - 1; ++j)
            for (int u = 0; u < (int)byrow[i][j].size(); ++u)
                cout << i << " " << j << " " << byrow[i][j][u].se << " " << byrow[i][j][u].fi << "\n";

    cout << f.Get(2) << "---\n";*/

    for (int i = 1; i < m - 1; ++i)
        for (int j = 1; j < n - 1; ++j)
        {
            sort(byrow[i][j].begin(), byrow[i][j].end(), com);
            sort(bycol[i][j].begin(), bycol[i][j].end(), com);

            int v(0);
            for (int u = 0; u < (int)bycol[i][j].size(); ++u)
            {
                //cout << i << " " << j << " " << bycol[i][j][u].se << " " << bycol[i][j][u].fi << ":\n";
                while (v < (int)byrow[i][j].size() && byrow[i][j][v].se >= bycol[i][j][u].se)
                {
                    f.Update(byrow[i][j][v].first + 1, 1);
                    //cout << byrow[i][j][v].second << " " << byrow[i][j][v].first << "\n";
                    ++v;
                }

                ans += f.Get(bycol[i][j][u].first + 1);
                //cout << ans << "\n";
            }

            while (v > 0)
            {
                --v;
                f.Update(byrow[i][j][v].first + 1, -1);
            }
        }

    return ans;
}

void Read()
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> a(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];
    cout << count_rectangles(a);
}

void Solve()
{
}

Compilation message (stderr)

rect.cpp: In function 'void read(T&)':
rect.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

• 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: 28 / 28