Submission #1256183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256183		biank	Rectangles (IOI19_rect)	C++20	59 / 100	1085 ms	1114112 KiB

rect

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const int INF = 1e9 + 20;

struct SparseTable {
    vector<vi> st;
    SparseTable() {}
    SparseTable(vi &a) {
        int log = 1;
        while ((1 << log) < sz(a)) log++;
        st.resize(log);
        st[0] = a;
        forn(i, log - 1) {
            st[i + 1].resize(sz(a), INF);
            forn(j, sz(a) - (1 << i)) {
                st[i + 1][j] = max(st[i][j], st[i][j + (1 << i)]);
            }
        }
    }
    int query(int l, int r) { //[l, r)
        if (r - l <= 0) return -INF;
        int log = 31 - __builtin_clz(r - l);
        return max(st[log][l], st[log][r - (1 << log)]);
    }
};

ll count_rectangles(vector<vi> a) {
    int n = sz(a), m = sz(a[0]);
    vector<vi> l(n, vi(m)), r(n, vi(m));
    vector<vi> d(n, vi(m)), u(n, vi(m));
    forn(i, n) forn(j, m) {
        int k = j - 1;
        while (k >= 0 && a[i][k] < a[i][j]) k = l[i][k];
        l[i][j] = k;
    }
    forn(i, n) dforn(j, m) {
        int k = j + 1;
        while (k < m && a[i][k] < a[i][j]) k = r[i][k];
        r[i][j] = k;
    }
    forn(i, m) forn(j, n) {
        int k = j - 1;
        while (k >= 0 && a[k][i] < a[j][i]) k = u[k][i];
        u[j][i] = k;
    }
    forn(i, m) dforn(j, n) {
        int k = j + 1;
        while (k < n && a[k][i] < a[j][i]) k = d[k][i];
        d[j][i] = k;
    }
    vector<SparseTable> minR(m), maxL(m);
    forn(j, m) {
        vi v(n);
        forn(i, n) v[i] = -r[i][j];
        minR[j] = SparseTable(v);
    }
    forn(j, m) {
        vi v(n);
        forn(i, n) v[i] = l[i][j];
        maxL[j] = SparseTable(v);
    }
    vector<SparseTable> minD(n), maxU(n);
    forn(i, n) {
        vi v(m);
        forn(j, m) v[j] = -d[i][j];
        minD[i] = SparseTable(v);
    }
    forn(i, n) {
        vi v(m);
        forn(j, m) v[j] = u[i][j];
        maxU[i] = SparseTable(v);
    }
    vector<tuple<int, int, int, int>> ret;
    auto check = [&](int i1, int i2, int j1, int j2) {
        if (i1 < 0 || i2 >= n || j1 < 0 || j2 >= m) return;
        if (i2 - i1 < 2 || j2 - j1 < 2) return;
        if (-minR[j1].query(i1 + 1, i2) < j2) return;
        if (maxL[j2].query(i1 + 1, i2) > j1) return;
        if (-minD[i1].query(j1 + 1, j2) < i2) return;
        if (maxU[i2].query(j1 + 1, j2) > i1) return;
        ret.eb(i1, i2, j1, j2);
    };
    forsn(i, 1, n - 1) forsn(j, 1, m - 1) {
        check(u[i + 1][j], i + 1, j - 1, r[i][j - 1]);
        check(u[i + 1][j], i + 1, l[i][j + 1], j + 1);
        check(i - 1, d[i - 1][j], l[i][j + 1], j + 1);
        check(i - 1, d[i - 1][j], j - 1, r[i][j - 1]);
        check(i - 1, d[i - 1][j], j - 1, r[d[i - 1][j] - 1][j - 1]);
        check(i - 1, d[i - 1][j], l[d[i - 1][j] - 1][j + 1], j + 1);
    }
    sort(all(ret));
    return unique(all(ret)) - begin(ret);
}

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