Submission #1078030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078030		Ignut	Rectangles (IOI19_rect)	C++14	27 / 100	5060 ms	100692 KiB

rect

// Ignut
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int INF = 1e9 + 123;
 
const int LOG = 10;
const int N = 777;
int min_h[N][N], max_h[N][N], min_v[N][N], max_v[N][N];
int minH[N][N][LOG], maxH[N][N][LOG], minV[N][N][LOG], maxV[N][N][LOG];
 
ll count_rectangles(vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            for (int ii = i; ii >= 0; ii --) {
                if (a[ii][j] > a[i][j]) break;
                min_v[i][j] = ii;
            }
            for (int ii = i; ii < n; ii ++) {
                if (a[ii][j] > a[i][j]) break;
                max_v[i][j] = ii;
            }
            for (int jj = j; jj >= 0; jj --) {
                if (a[i][jj] > a[i][j]) break;
                min_h[i][j] = jj;
            }
            for (int jj = j; jj < m; jj ++) {
                if (a[i][jj] > a[i][j]) break;
                max_h[i][j] = jj;
            }
        }
    }
    
    for (int j = 0; j < m; j ++) {
        for (int l = 0; l < n; l ++) {
            minH[j][l][0] = min_h[l][j];
            maxH[j][l][0] = max_h[l][j];
            minV[j][l][0] = min_v[l][j];
            maxV[j][l][0] = max_v[l][j];
        }
    }
    for (int e = 1; e < LOG; e ++) {
        for (int j = 0; j < m; j ++) {
            for (int l = 0; l < n; l ++) {
                minH[j][l][e] = min(minH[j][l][e - 1], minH[j][l + (1 << (e - 1))][e - 1]);
                maxH[j][l][e] = max(maxH[j][l][e - 1], maxH[j][l + (1 << (e - 1))][e - 1]);
                minV[j][l][e] = min(minV[j][l][e - 1], minV[j][l + (1 << (e - 1))][e - 1]);
                maxV[j][l][e] = max(maxV[j][l][e - 1], maxV[j][l + (1 << (e - 1))][e - 1]);
            }
        }
    }
 
    int res = 0;
    for (int u = 1; u < n - 1; u ++) {
        for (int d = u; d < n - 1; d ++) {
            int e = int(log2(d - u + 1));
            for (int l = 1; l < m - 1; l ++) {
                int mnh = INF, mxh = -INF, mnv = INF, mxv = -INF;
                for (int r = l; r < m - 1; r ++) {
                    // mnh = min(mnh, minH[r][u][d]);
                    // mxh = max(mxh, maxH[r][u][d]);
                    // mnv = min(mnv, minV[r][u][d]);
                    // mxv = max(mxv, maxV[r][u][d]);
                    mnh = min(mnh, min(minH[r][u][e], minH[r][d - (1 << e) + 1][e]));
                    mxh = max(mxh, max(maxH[r][u][e], maxH[r][d - (1 << e) + 1][e]));
                    mnv = min(mnv, min(minV[r][u][e], minV[r][d - (1 << e) + 1][e]));
                    mxv = max(mxv, max(maxV[r][u][e], maxV[r][d - (1 << e) + 1][e]));
 
                    if (mnh < l) break;
                    if (mnv < u) break;
                    if (mxv > d) break;
 
                    res += (mxh == r);
                }
            }
        } 
    }
 
    return res;
}

• 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