Submission #730999

#	Time	Username	Problem	Language	Result	Execution time	Memory
730999		danikoynov	Rectangles (IOI19_rect)	C++14	72 / 100	5048 ms	496564 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;
}

struct frame
{
    short x1, x2, y1, y2;
    frame(short _x1 = 0, short _x2 = 0, short _y1 = 0, short _y2 = 0)
    {
        x1 = _x1;
        x2 = _x2;
        y1 = _y1;
        y2 = _y2;
    }
};



vector < frame > row_frame, col_frame;



vector < frame > row_cell[maxn][maxn], col_cell[maxn][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];



    vector < frame > last_row;
    int cnt = 0;

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

        for (int right_col = m - 1; 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] &&
                    left_col + 1 < right_col)
            {
                cnt ++;
                //cout << "row " << row << " " << left_col + 1 << " :: " << right_col - 1 << endl;
                st.insert({left_col + 1, right_col - 1});
            }
        }

        vector < frame > new_row;
        for (int i = 0; i < last_row.size(); i ++)
        {
            pair < int, int > cur = make_pair(last_row[i].y1, last_row[i].y2);
            if (st.find(cur) == st.end())
            {
                row_frame.push_back(last_row[i]);
            }
            else
            {
                last_row[i].x2 ++;
                new_row.push_back(last_row[i]);
                st.erase(cur);
            }
        }

        for (pair < int, int > cur : st)
        {
            new_row.push_back(frame(row, row, cur.first, cur.second));
        }

        last_row = new_row;
    }
    for (frame cur : last_row)
        row_frame.push_back(cur);


    vector < frame > last_col;


    for (int col = 1; col < m - 1; col ++)
    {
        set < pair < int, int > > st;
        for (int left_row = 0; left_row < n; left_row ++)
        {
            int right_row = left_row + 1;
            while(right_row < n && h[left_row][col] > h[right_row][col])
                right_row ++;
            ///cout << "here " << row << " " << left_col << " " << right_col << endl;
            if (right_row != n && left_row + 1 < right_row)
            {
                cnt ++;
                ///cout << h[row][left_col] << " " << h[row][right_col] << endl;
                st.insert({left_row + 1, right_row - 1});
            }
        }

        for (int right_row = n - 1; right_row > 0; right_row --)
        {
            int left_row = right_row - 1;
            while(left_row >= 0 && h[right_row][col] > h[left_row][col])
                left_row --;
            ///cout << row << " :: " << left_col << " :: " << right_col << endl;
            if (left_row >= 0 && h[right_row][col] < h[left_row][col] &&
                    left_row + 1 < right_row)
            {
                cnt ++;
                //cout << "row " << row << " " << left_col + 1 << " :: " << right_col - 1 << endl;
                st.insert({left_row + 1, right_row - 1});
            }
        }

        vector < frame > new_col;
        for (int i = 0; i < last_col.size(); i ++)
        {
            pair < int, int > cur = make_pair(last_col[i].x1, last_col[i].x2);
            if (st.find(cur) == st.end())
            {
                col_frame.push_back(last_col[i]);
            }
            else
            {
                last_col[i].y2 ++;
                new_col.push_back(last_col[i]);
                st.erase(cur);
            }
        }

        for (pair < int, int > cur : st)
        {
            new_col.push_back(frame(cur.first, cur.second, col, col));
        }

        last_col = new_col;
    }
    for (frame cur : last_col)
        col_frame.push_back(cur);

    /**for (frame cur : last_col)
    {
        cout << "frame " << cur.x1 << " " << cur.x2 << " " << cur.y1 << " " << cur.y2 << endl;
    }*/

    if (cnt > 4 * n * m)
        exit(0);
    for (frame cur : row_frame)
    {
        for (int x = cur.x1; x <= cur.x2; x ++)
        {
            row_cell[x][cur.y2].push_back(cur);
        }
    }

    for (frame cur : col_frame)
    {
        for (int y = cur.y1; y <= cur.y2; y ++)
        {
            col_cell[cur.x2][y].push_back(cur);
        }
    }


    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {
            for (frame row : row_cell[i][j])
                for (frame col : col_cell[i][j])
                {
                    bool tf = false;
                    if (col.x1 >= row.x1 && col.x2 <= row.x2 &&
                            row.y1 >= col.y1 && row.y2 <= col.y2)
                        tf = true;

                    if (tf)
                    {

                        ans ++;
                    }
                }
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:145:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<frame>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for (int i = 0; i < last_row.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~
rect.cpp:207:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<frame>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for (int i = 0; i < last_col.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~

• 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