Submission #298860

#	Time	Username	Problem	Language	Result	Execution time	Memory
298860		Aldas25	Rectangles (IOI19_rect)	C++14	50 / 100	5008 ms	233084 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]);
}

int par[MAXN*MAXN], sz[MAXN*MAXN], mnR[MAXN*MAXN], mxR[MAXN*MAXN], mnC[MAXN*MAXN], mxC[MAXN*MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
void unite (int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    par[b] = a;
    sz[a] += sz[b];
    mnR[a] = min(mnR[a], mnR[b]);
    mnC[a] = min(mnC[a], mnC[b]);
    mxR[a] = max(mxR[a], mxR[b]);
    mxC[a] = max(mxC[a], mxC[b]);
}

int getId (int i, int j) {
    return i*m + j;
}

long long sub6(std::vector<std::vector<int> > a) {
    FOR(i, 0, n-1) FOR(j, 0, m-1) {
        int id = getId(i,j);
        par[id] = id;
        sz[id] = 1;
        mnR[id] = mxR[id] = i;
        mnC[id] = mxC[id] = j;
    }
    FOR(i, 0, n-1) FOR(j, 0, m-1) {
        if(a[i][j] == 1) continue;
        if (i < n-1 && a[i+1][j] == 0)
            unite(getId(i,j), getId(i+1,j));
        if (j < m-1 && a[i][j+1] == 0)
            unite(getId(i,j), getId(i, j+1));
    }
    ll ans = 0ll;
    FOR(i, 0, n-1) FOR(j, 0, m-1) {
        if (a[i][j] == 1) continue;
        int id = getId(i,j);
        if (find(id) != id) continue;
        if (mxR[id] == n-1 || mxC[id] == m-1 || mnR[id] == 0 || mnC[id] == 0) continue;
        if (sz[id] == (mxR[id] - mnR[id] + 1) * (mxC[id] - mnC[id] + 1))
            ans++;
    }
    return ans;
}

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

    bool s6 = true;
    FOR(i, 0 ,n-1) FOR(j, 0, m-1) if (a[i][j] > 1) s6 = false;

    if (s6) {
        return sub6(a);
    }

    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

4 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0


*/

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