Submission #1067936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067936		becaido	Rectangles (IOI19_rect)	C++17	27 / 100	323 ms	102740 KiB

rect

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "rect.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 205;

int n, m;
ll ans;
int a[SIZE][SIZE];
int U[SIZE][SIZE][SIZE], D[SIZE][SIZE][SIZE];
int L[SIZE][SIZE][SIZE], R[SIZE][SIZE][SIZE];

ll count_rectangles(vector<vector<int>> _a) {
    n = _a.size(), m = _a[0].size();
    FOR (i, 1, n) FOR (j, 1, m) a[i][j] = _a[i - 1][j - 1];

    FOR (i, 1, n) {
        vector<int> st;
        FOR (j, 1, m) {
            while (st.size() && a[i][j] > a[i][st.back()]) st.pop_back();
            L[i][i][j] = (st.size() ? st.back() + 1 : 1);
            st.pb(j);
            // debug(i, j, L[i][i][j]);
        }
        st.clear();
        for (int j = m; j >= 1; j--) {
            while (st.size() && a[i][j] > a[i][st.back()]) st.pop_back();
            R[i][i][j] = (st.size() ? st.back() - 1 : m);
            st.pb(j);
            // debug(i, j, R[i][i][j]);
        }
    }
    FOR (j, 1, m) {
        vector<int> st;
        FOR (i, 1, n) {
            while (st.size() && a[i][j] > a[st.back()][j]) st.pop_back();
            U[i][j][j] = (st.size() ? st.back() + 1 : 1);
            st.pb(i);
            // debug(i, j, U[i][j][j]);
        }
        st.clear();
        for (int i = n; i >= 1; i--) {
            while (st.size() && a[i][j] > a[st.back()][j]) st.pop_back();
            D[i][j][j] = (st.size() ? st.back() - 1 : n);
            st.pb(i);
            // debug(i, j, D[i][j][j]);
        }
    }

    FOR (u, 1, n) FOR (d, u + 1, n) FOR (j, 1, m) {
        L[u][d][j] = max(L[u][d - 1][j], L[d][d][j]);
        R[u][d][j] = min(R[u][d - 1][j], R[d][d][j]);
    }
    FOR (i, 1, n) FOR (l, 1, m) FOR (r, l + 1, m) {
        U[i][l][r] = max(U[i][l][r - 1], U[i][r][r]);
        D[i][l][r] = min(D[i][l][r - 1], D[i][r][r]);
    }

    ans = 0;
    FOR (u, 1, n) FOR (d, u + 2, n) FOR (l, 1, m) FOR (r, l + 2, m) {
        bool f = 1;
        // debug(u, d, l, r, D[u][l][r], U[d][l][r], R[u][d][l], L[u][d][r]);
        f &= (D[u][l + 1][r - 1] + 1 >= d);
        f &= (U[d][l + 1][r - 1] - 1 <= u);
        f &= (R[u + 1][d - 1][l] + 1 >= r);
        f &= (L[u + 1][d - 1][r] - 1 <= l);
        ans += f;
    }
    return ans;
}

/*
in1
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
out1
6
*/

• 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