제출 #229772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229772		combi1k1	Rectangles (IOI19_rect)	C++14	100 / 100	2934 ms	548276 KiB

rect

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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;
typedef vector<int> vi;
typedef vector<vi>  mtx;

int count_rectangles(mtx A) {
    int n = sz(A);
    int m = sz(A[0]);

    mtx l(n,vi(m,-1));
    mtx r(n,vi(m,-1));
    mtx u(n,vi(m,-1));
    mtx d(n,vi(m,-1));

    for(int i = 0 ; i < n ; ++i)    {
        stack<int>  lef;
        stack<int>  rig;

        for(int j = 0 ; j < m ; ++j)    {
            while (lef.size() && A[i][lef.top()] < A[i][j])
                lef.pop();
            
            if (lef.size()) l[i][j] = lef.top();

            lef.push(j);
        }
        for(int j = m - 1 ; j >= 0 ; --j)   {
            while (rig.size() && A[i][rig.top()] < A[i][j])
                rig.pop();
            
            if (rig.size()) r[i][j] = rig.top();

            rig.push(j);
        }
    }
    for(int j = 0 ; j < m ; ++j)    {
        stack<int>  lef;
        stack<int>  rig;

        for(int i = 0 ; i < n ; ++i)    {
            while (lef.size() && A[lef.top()][j] < A[i][j])
                lef.pop();
            
            if (lef.size()) u[i][j] = lef.top();

            lef.push(i);
        }
        for(int i = n - 1 ; i >= 0 ; --i)   {
            while (rig.size() && A[rig.top()][j] < A[i][j])
                rig.pop();
            
            if (rig.size()) d[i][j] = rig.top();

            rig.push(i);
        }
    }
    mtx LU(n,vi(m,-1));
    mtx RU(n,vi(m,-1));
    mtx UL(n,vi(m,-1));
    mtx DL(n,vi(m,-1));

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        if (l[i][j] >= 0)   {
            if      (i && l[i - 1][j] == l[i][j])   LU[i][j] = LU[i - 1][j];
            else if (i && r[i - 1][l[i][j]] == j)   LU[i][j] = RU[i - 1][l[i][j]];
            else    LU[i][j] = i;
        }
        if (r[i][j] >= 0)   {
            if      (i && r[i - 1][j] == r[i][j])   RU[i][j] = RU[i - 1][j];
            else if (i && l[i - 1][r[i][j]] == j)   RU[i][j] = LU[i - 1][r[i][j]];
            else    RU[i][j] = i;
        }
    }
    for(int j = 0 ; j < m ; ++j)
    for(int i = 0 ; i < n ; ++i)    {
        if (u[i][j] >= 0)   {
            if      (j && u[i][j - 1] == u[i][j])   UL[i][j] = UL[i][j - 1];
            else if (j && d[u[i][j]][j - 1] == i)   UL[i][j] = DL[u[i][j]][j - 1];
            else    UL[i][j] = j;
        }
        if (d[i][j] >= 0)   {
            if      (j && d[i][j - 1] == d[i][j])  DL[i][j] = DL[i][j - 1];
            else if (j && u[d[i][j]][j - 1] == i)  DL[i][j] = UL[d[i][j]][j - 1];
            else    DL[i][j] = j;
        }
    }
    unordered_set<ll>   ans;

    auto check = [&](int L,int R,int U,int D)   {
        if (L > R || U > D) return;
        if (L < 1 || R > n - 2) return;
        if (U < 1 || D > m - 2) return;
        
        if (!((r[R][U - 1] == D + 1 && RU[R][U - 1] <= L) || (l[R][D + 1] == U - 1 && LU[R][D + 1] <= L)))  return;
        if (!((d[L - 1][D] == R + 1 && DL[L - 1][D] <= U) || (u[R + 1][D] == L - 1 && UL[R + 1][D] <= U)))  return;

        ll  val = L;

        val *= 3000;    val += R;
        val *= 3000;    val += U;
        val *= 3000;    val += D;
        
        ans.insert(val);
    };

    for(int i = 1 ; i < n - 1 ; ++i)
    for(int j = 1 ; j < m - 1 ; ++j)    {
        if (u[i + 1][j] >= 0 && l[i][j + 1] >= 0)   check(u[i + 1][j] + 1,i,l[i][j + 1] + 1,j);
        if (u[i + 1][j] >= 0 && r[i][j - 1] >= 0)   check(u[i + 1][j] + 1,i,j,r[i][j - 1] - 1);
        
        int R = d[i - 1][j] - 1;
        if (R < i)  continue;

        if (l[i][j + 1] >= 0)   check(i,R,l[i][j + 1] + 1,j);
        if (l[R][j + 1] >= 0)   check(i,R,l[R][j + 1] + 1,j);

        if (r[i][j - 1] >= 0)   check(i,R,j,r[i][j - 1] - 1); 
        if (r[R][j - 1] >= 0)   check(i,R,j,r[R][j - 1] - 1);
    }
    return  ans.size();
}

• 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