Submission #229711

#	Time	Username	Problem	Language	Result	Execution time	Memory
229711		combi1k1	Rectangles (IOI19_rect)	C++14	0 / 100	6 ms	1024 KiB

rect

#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;

typedef pair<ii,ii> rec;

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

    mtx l(n,vi(m,-1));
    mtx u(n,vi(m,-1));
    mtx r(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 f[4];

    f[0].assign(n,vi(m,-1));
    f[1].assign(n,vi(m,-1));
    f[2].assign(n,vi(m,-1));
    f[3].assign(n,vi(m,-1));

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        if (i == 0)
            f[0][i][j] = (l[i][j] < 0),
            f[1][j][j] = (r[i][j] < 0);
        else    {
            if (l[i][j] < 0)    f[0][i][j] = i + 1;
            else    {
                if      (l[i - 1][j] == l[i][j])     f[0][i][j] = f[0][i - 1][j];
                else if (r[i - 1][l[i][j]] == j)     f[0][i][j] = f[1][i - 1][l[i][j]];
                else    f[0][i][j] = i;
            }
            if (r[i][j] < 0)    f[1][i][j] = i + 1;
            else    {
                if      (r[i - 1][j] == r[i][j])     f[1][i][j] = f[1][i - 1][j];
                else if (l[i - 1][r[i][j]] == j)     f[1][i][j] = f[0][i - 1][r[i][j]];
                else    f[1][i][j] = i;
            }
        }
    }
    for(int j = 0 ; j < m ; ++j)
    for(int i = 0 ; i < n ; ++i)    {
        if (j == 0)
            f[2][i][j] = (u[i][j] < 0),
            f[3][i][j] = (d[i][j] < 0);
        else    {
            if (u[i][j] < 0)    f[2][i][j] = j + 1;
            else    {
                if      (u[i][j - 1] == u[i][j])     f[2][i][j] = f[2][i][j - 1];
                else if (d[u[i][j]][j - 1] == i)     f[2][i][j] = f[3][u[i][j]][j - 1];
                else    f[2][i][j] = j;
            }
            if (d[i][j] < 0)    f[3][i][j] = j + 1;
            else    {
                if      (d[i][j - 1] == d[i][j])     f[3][i][j] = f[3][i][j - 1];
                else if (u[d[i][j]][j - 1] == i)     f[3][i][j] = f[2][d[i][j]][j - 1];
                else    f[3][i][j] = j;
            }
        }
    }
    return  6;
    set<rec> 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 > n - 2) return;
        
        if (u[R + 1][D] != L - 1 && d[L - 1][D] != R + 1)   return;
        if (l[R][D + 1] != U - 1 && r[R][U - 1] != D + 1)   return;

        if (A[R][U - 1] >= A[R][D + 1] && f[0][R][D + 1] > L)   return;
        if (A[R][U - 1] <= A[R][D + 1] && f[1][R][U - 1] > L)   return;
        if (A[L - 1][D] >= A[R + 1][D] && f[2][R + 1][D] > U)   return;
        if (A[L - 1][D] <= A[R + 1][D] && f[3][L - 1][D] > U)   return;

        ans.insert(rec(ii(L,R),ii(U,D)));
    };

    for(int i = 1 ; i < n - 1 ; ++i)
    for(int j = 1 ; j < m - 1 ; ++j)    {
        check(u[i + 1][j] + 1,i,l[i][j + 1] + 1,j);
        check(u[i + 1][j] + 1,i,j,r[i][j - 1] - 1);

        check(i,d[i - 1][j] - 1,l[i][j + 1] + 1,j);
        check(i,d[i - 1][j] - 1,j,r[i][j - 1] - 1);
    }
    return  ans.size();
}

• 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