Submission #207331

#	Time	Username	Problem	Language	Result	Execution time	Memory
207331		balbit	Rectangles (IOI19_rect)	C++14	27 / 100	2903 ms	188280 KiB

rect

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

#define ll long long
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(),x.end()

#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = ", _do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int MX = 205;

int vr[MX][MX][MX]; // Column, row 1, row 2
int vl[MX][MX][MX];
int hd[MX][MX][MX]; // Row, c1, c2
int hu[MX][MX][MX];

#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define FOR(i,a,b) for (int i = a; i<b; i++)

ll count_rectangles(vector<vector<int> > a) {
    int n = SZ(a);
    int m = SZ(a[0]);
    // build vr, vl
    REP(j,m) {
        REP(i,n){
            int &k = vr[j][i][i];
            for (k = j; k+1<m && a[i][k+1] < a[i][j]; ++k);
            RREP(it, i) {
                vr[j][it][i] = min(vr[j][it+1][i], vr[j][it][it]);
            }
        }

        REP(i,n){
            int &k = vl[j][i][i];
            for (k = j; k-1>=0 && a[i][k-1] < a[i][j]; --k);
            RREP(it, i) {
                vl[j][it][i] = max(vl[j][it+1][i], vl[j][it][it]);
            }
        }
    }

    // build hd, hu

    REP(i,n) {
        REP(j,m) {
            int &k = hd[i][j][j];
            for (k=i; k+1<n && a[k+1][j] < a[i][j]; ++k);
            RREP(it,j) {
                hd[i][it][j] = min(hd[i][it+1][j] , hd[i][it][it]);
            }
        }
        REP(j,m) {
            int &k = hu[i][j][j];
            for (k=i; k-1>=0 && a[k-1][j] < a[i][j]; --k);
            RREP(it,j) {
                hu[i][it][j] = max(hu[i][it+1][j] , hu[i][it][it]);
            }
        }
    }
    ll re = 0;
    FOR(r1,1,n-1) FOR(r2,1,n-1) FOR(c1,1,m-1) FOR(c2,1,m-1) {
        re += hd[r1-1][c1][c2] >=r2 && hu[r2+1][c1][c2] <= r1
            &&vr[c1-1][r1][r2] >=c2 && vl[c2+1][r1][r2] <= c1;
    }
    return re;
}

#ifdef BALBIT
signed main(){
    IOS();
    ll ro = count_rectangles({{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}});
    bug(ro);
}
#endif

• 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