Submission #730674

#	Time	Username	Problem	Language	Result	Execution time	Memory
730674		danikoynov	Rectangles (IOI19_rect)	C++14	27 / 100	5098 ms	1048576 KiB

rect

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

using namespace std;
typedef long long ll;


const int maxn = 710;

int n, m;
int h[maxn][maxn], lg[maxn];


struct sparse_table
{
    vector < vector < int > > table;

    sparse_table(){};
    void build_sparse_table(vector < int > &values)
    {
        int n = values.size();
        table.resize(lg[n]);
        for (int i = 0; i < lg[n]; i ++)
            table[i].resize(n);

        for (int i = 0; i < n; i ++)
            table[0][i] = values[i];

        for (int j = 1; j < lg[n]; j ++)
            for (int i = 0; i < n - (1 << j); i ++)
        {
            table[j][i] = max(table[j - 1][i],
                              table[j - 1][i + (1 << (j - 1))]);
        }

    }

    int query(int left, int right)
    {
        int len = lg[right - left + 1] - 1;
        return max(table[len][left], table[len][right - (1 << len) + 1]);
    }
};
sparse_table mrow[maxn], mcol[maxn];
long long count_rectangles(vector<vector<int> > a)
{
    n = a.size();
    m = a[0].size();
    for (int i = 1; i <= max(n, m); i ++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            h[i][j] = a[i][j];

    for (int i = 0; i < n; i ++)
    {
        ///mrow[i].build_sparse_table(a[i]);
        vector < int > values;
        for (int j = 0; j < m; j ++)
            values.push_back(a[i][j]);
        mrow[i].build_sparse_table(values);
    }
    for (int j = 0; j < m; j ++)
    {
        vector < int > values;
        for (int i = 0; i < n; i ++)
            values.push_back(a[i][j]);
        mcol[j].build_sparse_table(values);
    }


    /**for (int i = 0; i < n; i ++)
    {
        for (int j1 = 0; j1 < m; j1 ++)
        {
            mrow[i][j1][j1] = h[i][j1];
            for (int j2 = j1 + 1; j2 < m; j2 ++)
            {
                mrow[i][j1][j2] = max(mrow[i][j1][j2 - 1], h[i][j2]);
            }
        }
    }

    for (int j = 0; j < m; j ++)
        for (int i1 = 0; i1 < n; i1 ++)
        {
            mcol[j][i1][i1] = h[i1][j];
            for (int i2 = i1 + 1; i2 < n; i2 ++)
            {
                mcol[j][i1][i2] = max(mcol[j][i1][i2 - 1], h[i2][j]);
            }
        }*/
    /**cout << "-----------" << endl;
    for (int i = 0; i < n; i ++, cout << endl)
        for (int j = 0; j < m; j ++)
        cout << h[i][j] << " ";
    cout << "-----------" << endl;*/
    int ans = 0;
    for (int i = 1; i < n - 1; i ++)
        for (int j = 1; j < m - 1; j ++)
            for (int x = i; x < n - 1; x ++)
                for (int y = j; y < m - 1; y ++)
                {
                    /**int i = 4;
                    int x = 4;
                    int j = 2;
                    int y = 3;*/
                    bool tf = true;
                    for (int dx = 0; dx <= x - i && tf; dx ++)
                    {
                        int mx = mrow[i + dx].query(j, y), cx = i + dx;
                        //cout << mx << " " << i + dx << " " << j << " " << y << endl;
                        if (mx >= h[cx][j - 1] || mx >= h[cx][y + 1])
                            tf = false;
                    }


                    for (int dy = 0; dy <= y - j && tf; dy ++)
                    {
                        int mx = mcol[j + dy].query(i, x), cy = j + dy;
                        //cout << mx << " " << h[i - 1][cy] << " " << h[x + 1][cy] << endl;
                        if (mx >= h[i - 1][cy] || mx >= h[x + 1][cy])
                            tf = false;
                    }


                    /**for (int dx = 0; dx <= x - i && tf; dx ++)
                        for (int dy = 0; dy <= y - j && tf; dy ++)
                        {
                            int cx = i + dx, cy = j + dy;

                            if (h[cx][cy] >= h[cx][j - 1] || h[cx][cy] >= h[cx][y + 1])
                                tf = false;
                            if (i == 1 && j == 1 && x == 2 && y == 1)
                            {
                                //cout << dx << " : " << dy << " : " << tf << endl;
                                ///cout << h[cx][cy] << " -- " << h[cx][j - 1] << " -- " << h[cx][y + 1] << endl;
                            }
                            if (h[cx][cy] >= h[i - 1][cy] || h[cx][cy] >= h[x + 1][cy])
                                tf = false;

                        }*/
                    if (tf)
                    {
                        ///cout << i << " " << j << " " << x << " " << y << endl;
                        ans ++;
                    }
                }

    return ans;
}

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