제출 #712166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712166		boris_mihov	Rectangles (IOI19_rect)	C++17	0 / 100	5094 ms	92716 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 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();
        }
    }
}

llong count_rectangles(std::vector <std::vector <int>> A) 
{
    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];
        }
    }

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

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

    // 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])
            {
                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])
            {
                st[row].pop();
            }

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

    llong ans = 0;
    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)
            {
                need = std::min(need, minRight[col]);
                if (col < m && (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--;
                }

                if (col + 1 < need)
                {
                    ans += fenwick.query(need) - fenwick.query(col + 1);
                }

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

	return ans;
}

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