Submission #745550

#	Time	Username	Problem	Language	Result	Execution time	Memory
745550		MohamedAliSaidane	Rectangles (IOI19_rect)	C++14	27 / 100	5063 ms	397148 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;

typedef vector<int> vi;

#define pb push_back
#define ff first
#define ss second

const int nax = 2505;
const int nax2 = 205;

int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};

int n, m;
vector<vi> A;
ll ans = 0ll;
int LG[nax];
int spr[nax][nax][12];
int spc[nax][nax][12];
int prefr[nax2][nax2][nax2];
int prefc[nax2][nax2][nax2];

int maxir(int row, int l, int r)
{
    int j = LG[r - l + 1];
    return max(spr[row][l][j], spr[row][r - (1 << j) + 1][j]);
}
int maxic(int col, int l, int r)
{
    int j = LG[r - l + 1];
    return max(spc[col][l][j], spc[col][r - (1 << j) + 1][j]);
}

void init()
{
    LG[1] = 0;
    for(int i = 2; i < nax; i++)
        LG[i] = LG[i/2] + 1;
    for(int row = 0; row < n; row++)
    {
        for(int col = 0; col < m; col++)
            spr[row][col][0] = spc[col][row][0] =  A[row][col];
    }
    for(int j = 1; j < 12; j++)
    {
        for(int row = 0; row < n; row++)
        {
            for(int col = 0; col < m; col++)
            {
                spr[row][col][j] = max(spr[row][col][j - 1], spr[row][col + (1 << (j - 1))][j - 1]);
                spc[col][row][j] = max(spc[col][row][j - 1], spc[col][row + (1 << (j - 1))][j - 1]);
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j =  i + 2;  j < n; j++)
        {
            for(int k = 0; k < m; k++)
            {
                prefr[i][j][k + 1] = prefr[i][j][k] + (min(A[i][k], A[j][k]) <= maxic(k, i + 1, j -1)) ;
            }
        }
    }
    for(int i = 0 ;i < m; i ++)
    {
        for(int j = i + 2; j < m; j++)
        {
            for(int k = 0; k < n; k++)
            {
                prefc[i][j][k + 1] = prefc[i][j][k] + (min(A[k][i], A[k][j]) <= maxir(k, i + 1, j - 1));
            }
        }
    }
}

ll count_rectangles(vector<vi> a)
{
    n = a.size();
    m = a[0].size();
    A= a;
    if(n <= 2 || m <= 2)
        return 0ll;
    init();
    for(int i = 1;  i < n - 1;i ++)
    {
        for(int j = i; j < n - 1; j++)
        {
            for(int k = 1; k < m - 1; k++)
            {
                for(int l = k; l < m - 1; l++)
                {
                    if(prefr[i - 1][j + 1][l + 1] - prefr[i - 1][j + 1][k] == 0
                       && prefc[k - 1][l + 1][j + 1] - prefc[k - 1][l + 1][i] == 0)
                       {
                            ans++;
                            //;cout << i << ' ' << k << ' ' << j << ' '<< l << '\n';
                       }
                }
            }
        }
    }
    return ans;
}
/*
int32_t main()
{
    freopen("01.in", "r", stdin);
    int N, M;
    cin >> N >> M;
    vector<vi> a(N);
    for(int i = 0; i < N; i++)
    {
        a[i].resize(M);
        for(int j = 0; j < M; j++)
            cin >> a[i][j];
    }
    cout << count_rectangles(a);
}
*/

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