Submission #730706

#	Time	Username	Problem	Language	Result	Execution time	Memory
730706		danikoynov	Rectangles (IOI19_rect)	C++14	72 / 100	5126 ms	734796 KiB

rect

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

using namespace std;
typedef long long ll;


const int maxn = 2510;

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];

int check_array(int left, int right)
{
    ///cout << left << " : " << right << endl;
    int ans = 0;
    for (int i = left; i <= right; i ++)
        for (int j = i; j <= right; j ++)
        {
            int mx = mrow[1].query(i, j);
            //cout << i << " --- " << j << " -- " << mx << endl;
            if (mx < h[1][i - 1] && mx < h[1][j + 1])
                ans ++;
        }
    return ans;
}

bool check_row(int row, int left, int right)
{
    int mx = mrow[row].query(left, right);
    if (mx < h[row][left - 1] && mx < h[row][right + 1])
        return true;
        return false;
}

bool check_col(int col, int up, int down)
{
    int mx = mcol[col].query(up, down);
    if (mx < h[up - 1][col] && mx < h[down + 1][col])
        return true;
    return false;
}
int check(int row, int left, int right)
{
    if (left > right)
        return 0;

        int ans = 0;
        ///cout << row << " :: " << left << " " << right << endl;
    for (int i = row; i < n - 1; i ++)
    {

        if (check_row(i, left, right) == false)
            break;
            bool tf = true;

        for (int j = left; j <= right; j ++)
        {
            if (!check_col(j, row, i))
            {
                tf = false;
                break;
            }
        }

        if (tf)
            ans ++;
    }

    return ans;
}
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);
    }


    if (n == 3)
    {
        int ans = 0, len = 0;
        for (int j = 1; j < m - 1; j ++)
        {
            ///cout << j << " :: " << len << endl;
            if (h[1][j] < h[0][j] && h[1][j] < h[2][j])
                len ++;
            else
            {
                if (len > 0)
                    ans += check_array(j - len, j - 1);
                len = 0;
            }
        }
        if (len > 0)
            ans += check_array(m - len - 1, m - 2);

        return ans;
    }

    int ans = 0;
    for (int row = 1; row < n - 1; row ++)
    {
        for (int left_col = 0; left_col < m; left_col ++)
        {
            int right_col = left_col + 1;
            while(right_col < m - 1 && h[row][left_col] > h[row][right_col])
                right_col ++;
            ///cout << "here " << row << " " << left_col << " " << right_col << endl;
            if (right_col != m)
                ans += check(row, left_col + 1, right_col - 1);
        }

        for (int right_col = m - 2; right_col > 0; right_col --)
        {
            int left_col = right_col - 1;
            while(left_col >= 0 && h[row][right_col] > h[row][left_col])
                left_col --;
                ///cout << row << " :: " << left_col << " :: " << right_col << endl;
            if (left_col >= 0 && h[row][right_col] < h[row][left_col])
                ans += check(row, left_col + 1, right_col - 1);
        }
    }

    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'bool check_row(int, int, int)':
rect.cpp:64:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   64 |     if (mx < h[row][left - 1] && mx < h[row][right + 1])
      |     ^~
rect.cpp:66:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   66 |         return false;
      |         ^~~~~~
rect.cpp: In function 'int check(int, int, int)':
rect.cpp:78:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |     if (left > right)
      |     ^~
rect.cpp:81:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   81 |         int ans = 0;
      |         ^~~
rect.cpp:86:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |         if (check_row(i, left, right) == false)
      |         ^~
rect.cpp:88:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   88 |             bool tf = true;
      |             ^~~~

• 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