Submission #731031

#	Time	Username	Problem	Language	Result	Execution time	Memory
731031		danikoynov	Rectangles (IOI19_rect)	C++14	100 / 100	2418 ms	784448 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 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;

int fen[maxn];

void add(int v, int val)
{
    v ++;
    for (int i = v; i < maxn; i += (i & -i))
        fen[i] += val;
}

int sum(int v)
{
    v ++;
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}


vector < pair < int, int > > drow[maxn][maxn], dcol[maxn][maxn];
int pt_drow[maxn][maxn], pt_dcol[maxn][maxn];
int act_pair[maxn][maxn];
long long count_rectangles(vector<vector<int> > a)
{
    n = a.size();
    m = a[0].size();

    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 ++)
    {

        vector < frame > new_row;
        stack < int > st;
        for (int left_col = m - 1; left_col >= 0; left_col --)
        {
            while(!st.empty() && h[row][left_col] > h[row][st.top()])
                st.pop();
            //while(right_col < m && h[row][left_col] > h[row][right_col])
            //  right_col ++;
            int right_col = m;
            if (!st.empty())
                right_col = st.top();
            ///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;
                pt_drow[row][right_col - 1] ++;
                if (act_pair[left_col + 1][right_col - 1] != 0)
                    act_pair[left_col + 1][right_col - 1] = 2;
                else
                {
                    act_pair[left_col + 1][right_col - 1] = 1;
                    new_row.push_back(frame(row, row, left_col + 1, right_col - 1));
                }
            }
            st.push(left_col);
        }
        while(!st.empty())
            st.pop();
        for (int right_col = 0; right_col < m; right_col ++)
        {
            while(!st.empty() && h[row][right_col] > h[row][st.top()])
                st.pop();
            int left_col = -1;
            if (!st.empty())
                left_col = st.top();
            ///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 ++;
                pt_drow[row][right_col - 1] ++;
                if (act_pair[left_col + 1][right_col - 1] != 0)
                    act_pair[left_col + 1][right_col - 1] = 2;
                else
                {
                    act_pair[left_col + 1][right_col - 1] = 1;
                    new_row.push_back(frame(row, row, left_col + 1, right_col - 1));
                }
            }
            st.push(right_col);
        }

        for (int i = 0; i < last_row.size(); i ++)
        {
            ///pair < int, int > cur = make_pair(last_row[i].y1, last_row[i].y2);
            if (act_pair[last_row[i].y1][last_row[i].y2] != 2)
            {
                act_pair[last_row[i].y1][last_row[i].y2] = 0;
                row_frame.push_back(last_row[i]);
            }
            else
            {
                act_pair[last_row[i].y1][last_row[i].y2] = 1;
                last_row[i].x2 ++;
                new_row.push_back(last_row[i]);
            }
        }


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

    vector < frame > last_col;

    for (int i = 0; i < m; i ++)
        for (int j = 0; j < m; j ++)
            act_pair[i][j] = 0;
    for (int col = 1; col < m - 1; col ++)
    {
        vector < frame > new_col;
        stack < int > st;
        for (int left_row = n - 1; left_row >= 0; left_row --)
        {
            while(!st.empty() && h[left_row][col] > h[st.top()][col])
                st.pop();
            int right_row = n;
            if (!st.empty())
                right_row = st.top();

            ///cout << "here " << row << " " << left_col << " " << right_col << endl;
            if (right_row != n && left_row + 1 < right_row)
            {
                cnt ++;
                pt_dcol[right_row - 1][col] ++;

                if (act_pair[left_row + 1][right_row - 1] != 0)
                    act_pair[left_row + 1][right_row - 1] = 2;
                else
                {
                    act_pair[left_row + 1][right_row - 1] = 1;
                    new_col.push_back(frame(left_row + 1, right_row - 1, col, col));
                }
            }
            st.push(left_row);
        }
        while(!st.empty())
            st.pop();
        for (int right_row = 0; right_row < n; right_row ++)
        {
            while(!st.empty() && h[right_row][col] > h[st.top()][col])
                st.pop();
            int left_row = -1;
            if (!st.empty())
                left_row = st.top();

            ///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 ++;
                pt_dcol[right_row - 1][col] ++;
                //cout << "row " << row << " " << left_col + 1 << " :: " << right_col - 1 << endl;

                if (act_pair[left_row + 1][right_row - 1] != 0)
                    act_pair[left_row + 1][right_row - 1] = 2;
                else
                {
                    act_pair[left_row + 1][right_row - 1] = 1;
                    new_col.push_back(frame(left_row + 1, right_row - 1, col, col));
                }
            }
            st.push(right_row);
        }


        for (int i = 0; i < last_col.size(); i ++)
        {
            if (act_pair[last_col[i].x1][last_col[i].x2] != 2)
            {
                act_pair[last_col[i].x1][last_col[i].x2] = 0;
                col_frame.push_back(last_col[i]);
            }
            else
            {
                act_pair[last_col[i].x1][last_col[i].x2] = 1;
                last_col[i].y2 ++;
                new_col.push_back(last_col[i]);
            }
        }

        swap(new_col, last_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;
    }*/

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
        {
            drow[i][j].resize(pt_drow[i][j]);
            dcol[i][j].resize(pt_dcol[i][j]);
            pt_drow[i][j] = pt_dcol[i][j] = 0;
        }
    ///exit(0);
    for (frame cur : row_frame)
    {
        for (int x = cur.x1; x <= cur.x2; x ++)
        {
            drow[x][cur.y2][pt_drow[x][cur.y2] ++] = {x - cur.x1, cur.y2 - cur.y1};
        }
    }

    for (frame cur : col_frame)
    {
        for (int y = cur.y1; y <= cur.y2; y ++)
        {
            dcol[cur.x2][y][pt_dcol[cur.x2][y] ++] = {cur.x2 - cur.x1, y - cur.y1};
        }
    }


    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
        {


            sort(drow[i][j].begin(), drow[i][j].end());
            sort(dcol[i][j].begin(), dcol[i][j].end());

            int pt = 0;
            for (int pos = 0; pos < drow[i][j].size(); pos ++)
            {

                while(pt < dcol[i][j].size() && drow[i][j][pos].first >= dcol[i][j][pt].first)
                {

                    add(dcol[i][j][pt].second, 1);
                    ///cout << sum(max(n, m)) << endl;
                    pt ++;
                }
                /**for (int j = 0; j < pt; j ++)
                {
                    if (drow[i][j][pos].second <= dcol[i][j][j].second)
                        ans ++;
                }*/
                ans = ans + pt - sum(drow[i][j][pos].second - 1);


            }
            for (int pos = 0; pos < pt; pos ++)
                add(dcol[i][j][pos].second, -1);
            /**for (pair < int, int > col : dcol)
                cout << col.first << " " << col.second << endl;
            cout << "-----------" << endl;*/

            /**for (pair < int, int > row : drow)
                for (pair < int, int > col : dcol)
            {
                if (row.first >= col.first && col.second >= row.second)
                    ans ++;
            }*/

            /**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:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<frame>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 0; i < last_row.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~
rect.cpp:208:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<frame>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |         for (int i = 0; i < last_col.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~
rect.cpp:269:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  269 |             for (int pos = 0; pos < drow[i][j].size(); pos ++)
      |                               ~~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:272:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  272 |                 while(pt < dcol[i][j].size() && drow[i][j][pos].first >= dcol[i][j][pt].first)
      |                       ~~~^~~~~~~~~~~~~~~~~~~

• 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