Submission #1237153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237153		Ghulam_Junaid	Rectangles (IOI19_rect)	C++20	27 / 100	5095 ms	42832 KiB

rect

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

typedef long long ll;

const int N = 705, LG = 10;
int n, m, row[N][N][LG], col[N][N][LG];

int get_row(int r, int c1, int c2){
    int lg = 31 - __builtin_clz(c2 - c1 + 1);
    return max(row[r][c1][lg], row[r][c2 - (1 << lg) + 1][lg]);
}

int get_col(int c, int r1, int r2){
    int lg = 31 - __builtin_clz(r2 - r1 + 1);
    return max(col[c][r1][lg], col[c][r2 - (1 << lg) + 1][lg]);
}

ll count_rectangles(vector<vector<int>> a){
    n = a.size(), m = a[0].size();
    ll ans = 0;
    if (n < 3 or m < 3) return 0;

    for (int i = 1; i + 1 < n; i ++){
        for (int j = 1; j + 1 < m; j ++)
            row[i][j][0] = a[i][j];
        for (int j = 1; j < LG; j ++)
            for (int k = 1; k + 1 < m and k + (1 << (j - 1)) < m; k ++)
                row[i][k][j] = max(row[i][k][j - 1], row[i][k + (1 << (j - 1))][j - 1]);
    }

    for (int i = 1; i + 1 < m; i ++){
        for (int j = 1; j + 1 < n; j ++)
            col[i][j][0] = a[j][i];
        for (int j = 1; j < LG; j ++)
            for (int k = 1; k + 1 < n and k + (1 << (j - 1)) < n; k ++)
                col[i][k][j] = max(col[i][k][j - 1], col[i][k + (1 << (j - 1))][j - 1]);
    }
    
    bool good[n] = {};
    for (int c1 = 1; c1 + 1 < m; c1 ++){
        for (int c2 = c1; c2 + 1 < m; c2 ++){
            memset(good, 0, sizeof good);

            for (int r = 1; r + 1 < n; r ++){
                int mx = get_row(r, c1, c2);
                good[r] = (a[r][c1 - 1] > mx and a[r][c2 + 1] > mx);
            }

            for (int r1 = 1; r1 + 1 < n; r1 ++){
                if (!good[r1]) continue;
                for (int r2 = r1; r2 + 1 < n; r2 ++){
                    if (!good[r2]) break;
                    bool all_good = 1;
                    for (int c = c1; c <= c2; c ++){
                        int mx = get_col(c, r1, r2);
                        all_good &= (a[r1 - 1][c] > mx and a[r2 + 1][c] > mx);
                    }

                    ans += all_good;
                }
            }
        }
    }

    return ans;
}

• 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