Submission #222932

#	Time	Username	Problem	Language	Result	Execution time	Memory
222932		MrDomino	Rectangles (IOI19_rect)	C++14	59 / 100	5072 ms	169212 KiB

rect

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

using namespace std;

typedef long long ll;

class RMQ
{
private:
    int n;
    vector<int> lg;
    vector<vector<int>> rmq;
public:
    RMQ(vector<int> a)
    {
        n = (int) a.size();
        lg.resize(n + 1, 0);
        for (int i = 2; i <= n; i++)
        {
            lg[i] = 1 + lg[i / 2];
        }
        rmq.resize(lg[n] + 1);
        for (int k = 0; k < (int) rmq.size(); k++)
        {
            rmq[k].resize(n);
        }
        for (int i = 0; i < n; i++)
        {
            rmq[0][i] = a[i];
        }
        for (int k = 1; k < (int) rmq.size(); k++)
        {
            for (int i = 0; i + (1 << k) - 1 < n; i++)
            {
                rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int get(int l, int r)
    {
        if (l > r)
        {
            return -1;
        }
        int k = lg[r - l + 1];
        return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
    }
};

long long count_rectangles(vector<vector<int>> a)
{
    ll sol = 0;
    int n = (int) a.size();
    int m = (int) a[0].size();
    vector<RMQ> rmq;
    for (int i = 0; i < n; i++)
    {
        rmq.push_back(RMQ(a[i]));
    }
    for (int r1 = 1; r1 < n - 1; r1++)
    {
        vector<int> mx(m);
        vector<int> f(m, m - 1);
        vector<int> s(m, 0);
        for (int r2 = r1; r2 < n - 1; r2++)
        {
            for (int j = 0; j < m; j++)
            {
                mx[j] = max(mx[j], a[r2][j]);
            }
            for (int i = 1; i < m - 1; i++)
            {
                while (rmq[r2].get(i, f[i]) >= a[r2][i - 1])
                {
                    f[i]--;
                }
                while (rmq[r2].get(s[i], i) >= a[r2][i + 1])
                {
                    s[i]++;
                }
            }
            vector<bool> ok(m);
            for (int j = 0; j < m; j++)
            {
                ok[j] = (mx[j] < min(a[r1 - 1][j], a[r2 + 1][j]));
            }
            for (int c1 = 1; c1 < m - 1; c1++)
            {
                if (ok[c1])
                {
                    for (int c2 = c1; c2 < m - 1; c2++)
                    {
                        if (ok[c2] == 0)
                        {
                            break;
                        }
                        if (c2 <= f[c1] && s[c2] <= c1)
                        {
                            sol++;
                        }
                    }
                }
            }
        }
    }
    return sol;
}

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