Submission #712182

#	Time	Username	Problem	Language	Result	Execution time	Memory
712182		boris_mihov	Rectangles (IOI19_rect)	C++17	50 / 100	5053 ms	221356 KiB

rect

#include "rect.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <stack>
#include <queue>

typedef long long llong;
const int MAXN = 2500 + 10;
const int INF  = 1e9;

int n, m;
struct BIT
{
    int tree[MAXN], max;
    inline void reset(const int &_max)
    {
        max = _max;
        std::fill(tree + 1, tree + 1 + max, 0);
    }

    inline void update(const int &pos, const int &value)
    {
        for (int idx = pos ; idx <= max ; idx += idx & (-idx))
        {
            tree[idx] += value;
        }
    }

    inline int query(const int &pos)
    {
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }
};

BIT fenwick;
int a[MAXN][MAXN];
int p[MAXN][MAXN];
int up[MAXN][MAXN];
int left[MAXN][MAXN];
int down[MAXN][MAXN];
int right[MAXN][MAXN];
std::stack <int> st[MAXN];
std::queue <int> q[MAXN];
int minRight[MAXN];
int maxLeft[MAXN];
bool isIN[MAXN];

void clearStacks()
{
    for (int i = 1 ; i <= std::max(n, m) ; ++i)
    {
        while (!st[i].empty())
        {
            st[i].pop();
        }
    }
}

inline int getSum(int r1, int c1, int r2, int c2)
{
    --r1; --c1;
    return p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1];
}

inline int getSum2(int r1, int c1, int r2, int c2)
{
    --r1; --c1;
    return (r2 - r1) * (c2 - c1) - (p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1]);
}


llong count_rectangles(std::vector <std::vector <int>> A) 
{
    bool zeroOne = true;
    n = A.size(); m = A[0].size();
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            a[i][j] = A[i - 1][j - 1];
            p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
            zeroOne &= (a[i][j] < 2);
        }
    }

    for (int i = 0 ; i <= m + 1 ; ++i)
    {
        a[0][i] = a[n + 1][i] = INF;
    }

    for (int i = 0 ; i <= n + 1 ; ++i)
    {
        a[i][0] = a[i][m + 1] = INF;
    }

    if (n <= 2 || m <= 2)
    {
        return 0;
    }

    // up
    for (int i = 1 ; i <= m ; ++i)
    {
        st[i].push(0);
    }

    for (int row = 1 ; row <= n ; ++row)
    {
        for (int col = 1 ; col <= m ; ++col)
        {
            while (!st[col].empty() && a[st[col].top()][col] < a[row][col])
            {
                st[col].pop();
            }

            up[row][col] = st[col].top();
            st[col].push(row);
        }
    }

    // down
    clearStacks();
    for (int i = 1 ; i <= m ; ++i)
    {
        st[i].push(n + 1);
    }

    for (int row = n ; row >= 1 ; --row)
    {
        for (int col = 1 ; col <= m ; ++col)
        {
            while (!st[col].empty() && (a[st[col].top()][col] < a[row][col] || (zeroOne && a[st[col].top()][col] == a[row][col])))
            {
                st[col].pop();
            }

            down[row][col] = st[col].top();
            st[col].push(row);
        }
    }

    // left
    clearStacks();
    for (int i = 1 ; i <= n ; ++i)
    {
        st[i].push(0);
    }

    for (int row = 1 ; row <= n ; ++row)
    {
        for (int col = 1 ; col <= m ; ++col)
        {
            while (!st[row].empty() && a[row][st[row].top()] < a[row][col])
            {
                st[row].pop();
            }

            left[row][col] = st[row].top();
            st[row].push(col);
        }
    }

    // right
    clearStacks();
    for (int i = 1 ; i <= n ; ++i)
    {
        st[i].push(m + 1);
    }

    for (int row = 1 ; row <= n ; ++row)
    {
        for (int col = m ; col >= 1 ; --col)
        {
            while (!st[row].empty() && (a[row][st[row].top()] < a[row][col] || (zeroOne && a[row][st[row].top()] == a[row][col])))
            {
                st[row].pop();
            }

            right[row][col] = st[row].top();
            st[row].push(col);
        }
    }

    llong ans = 0;
    if (zeroOne)
    {
        for (int r1 = 2 ; r1 <= n ; ++r1)
        {
            for (int c1 = 2 ; c1 <= m ; ++c1)
            {
                if (a[r1 - 1][c1] == 0 || a[r1][c1 - 1] == 0 || a[r1][c1] == 1)
                {
                    continue;
                }

                int c2 = right[r1][c1] - 1;
                if (c2 < m)
                {
                    int r2 = down[r1][c2] - 1;
                    if (r2 < n && getSum(r1, c1, r2, c2) == 0 && getSum2(r1 - 1, c1, r1 - 1, c2) == 0 && getSum2(r1, c1 - 1, r2, c1 - 1) == 0 && getSum2(r2 + 1, c1, r2 + 1, c2) == 0 && getSum2(r1, c2 + 1, r2, c2 + 1) == 0)
                    {
                        ans++;
                    }
                }
            }
        }

        return ans;
    }
 
    for (int row1 = 1 ; row1 + 2 <= n ; ++row1)
    {
        for (int col = 1 ; col <= m ; ++col)
        {
            maxLeft[col] = 0;
            minRight[col] = INF;
        }

        for (int row2 = row1 + 2 ; row2 <= n ; ++row2)
        {
            for (int col = 1 ; col <= m ; ++col)
            {
                maxLeft[col] = std::max(maxLeft[col], left[row2 - 1][col]);
                minRight[col] = std::min(minRight[col], right[row2 - 1][col]);
                while (!q[col].empty()) q[col].pop();
                isIN[col] = false;
            }

            fenwick.reset(m);
            int need = m;
            int ptr = m;

            for (int col = m ; col >= 1 ; --col)
            {
                if (col != m)
                {
                    if (down[row1][col + 1] < row2 || up[row2][col + 1] > row1)
                    {
                        need = col + 1;
                    }
                }

                while (!q[col].empty())
                {
                    int top = q[col].front();
                    if (isIN[top]) fenwick.update(top, -1);
                    isIN[top] = false;
                    q[col].pop();    
                }

                while (ptr > need)
                {
                    if (isIN[ptr])
                    {
                        fenwick.update(ptr, -1);
                        isIN[ptr] = false;
                    }

                    ptr--;
                }

                int to = std::min(need, minRight[col]);
                if (col + 1 != to)
                {
                    ans += fenwick.query(to) - isIN[col + 1];
                }

                isIN[col] = true;
                fenwick.update(col, 1);
                if (maxLeft[col]) q[maxLeft[col] - 1].push(col);
            }
        }
    }

	return ans;
}

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