제출 #298854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298854		Aldas25	Rectangles (IOI19_rect)	C++14	37 / 100	5097 ms	328956 KiB

rect

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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 3510, MAXK = 13;

int n, m;
int colMax[MAXN][MAXN][MAXK];
int rowMax[MAXN][MAXN][MAXK];
int lg[MAXN];

void buildST() {
    FOR(i, 2, MAXN-1) lg[i] = lg[i/2]+1;
    FOR(j, 1, MAXK-1) FOR(k, 0, m-1) for (int i = 0; i + (1<<j) <= n; i++) {
        colMax[k][i][j] = max(colMax[k][i][j-1], colMax[k][i + (1<<(j-1))][j-1]);
    }
    FOR(j, 1, MAXK-1) FOR(k, 0, n-1) for (int i = 0; i + (1<<j) <= m; i++) {
        rowMax[k][i][j] = max(rowMax[k][i][j-1], rowMax[k][i + (1<<(j-1))][j-1]);
    }
}

int getColMax (int k, int fr, int to) {
    int j = lg[to-fr+1];
    return max(colMax[k][fr][j], colMax[k][to - (1<<j)+ 1][j]);
}
int getRowMax (int k, int fr, int to) {
    int j = lg[to-fr+1];
    return max(rowMax[k][fr][j], rowMax[k][to - (1<<j)+ 1][j]);
}

long long count_rectangles(std::vector<std::vector<int> > a) {
    n = (int)a.size();
    m = (int)a[0].size();

    FOR(i, 0, n-1) FOR(j, 0, m-1) colMax[j][i][0] = rowMax[i][j][0] = a[i][j];
    buildST();

    /*FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(r2, r1, n-1) {
        cout << " colMax, col: " << c1 << " ["<<r1<<", "<<r2<<"]   mx= " << getColMax(c1, r1, r2) << endl;
     }
    FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(c2, c1, m-1) {
        cout << " rowMax, row: " << r1 << " ["<<c1<<", "<<c2<<"]   mx= " << getRowMax(r1, c1, c2) << endl;
     }*/

    ll ans = 0ll;
    FOR(r1, 1, n-2) FOR(c1, 1, m-2) FOR(r2, r1, n-2) FOR(c2, c1, m-2) {

        bool ok = true;
        /*FOR(i, r1, r2) FOR(j, c1, c2) {
            int mnH = a[i][c1-1];
            mnH = min(mnH, a[i][c2+1]);
            mnH = min(mnH, a[r1-1][j]);
            mnH = min(mnH, a[r2+1][j]);
            if(a[i][j] >= mnH) {
                ok = false;
                break;
            }
        }*/

        FOR(i, r1, r2) {
            int mnH = min(a[i][c1-1], a[i][c2+1]);
            int mxH = getRowMax(i, c1, c2);
            if (mxH >= mnH) {
                ok = false;
                break;
            }
        }
        if (ok) {
            FOR(j, c1, c2) {
                int mnH = min(a[r1-1][j], a[r2+1][j]);
                int mxH = getColMax(j, r1, r2);
                if(mxH >= mnH) {
                    ok = false;
                    break;
                }
            }
        }


        if (ok) ans++;

    }

	return ans;
}

/*

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
ans:
6


*/

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