Submission #610722

#	Time	Username	Problem	Language	Result	Execution time	Memory
610722		lorenzoferrari	Rectangles (IOI19_rect)	C++17	37 / 100	5110 ms	359296 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

#define UP 0
#define LEFT 1
#define DOWN 2
#define RIGHT 3

struct SparseTable {
    static const int LG = 13;
    int n;
    vector<array<int, LG>> st;
    SparseTable() {}
    SparseTable(vector<int> v) : n(v.size()) {
        st.resize(n);
        for (int i = 0; i < n; ++i) st[i][0] = v[i];
        for (int j = 1; j < LG; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }
    int query(int l, int r) {
        // [l, r)
        int lg = 31 - __builtin_clz(r - l);
        return max(st[l][lg], st[r - (1 << lg)][lg]);
    }
};

vector<int> next_geq_val(vector<int> v) {
    int n = v.size();
    stack<pair<int, int>> st;
    st.push({1e9, n});
    vector<int> ans(n);
    for (int i = n-1; i >= 0; --i) {
        while (st.top().first < v[i]) st.pop();
        ans[i] = st.top().second;
        st.push({v[i], i});
    }
    return ans;
}

vector<int> prev_geq_val(vector<int> v) {
    int n = v.size();
    reverse(v.begin(), v.end());
    auto r = next_geq_val(v);
    reverse(r.begin(), r.end());
    for (int& i : r) {
        i = n - 1 - i;
    }
    return r;
}

LL count_rectangles(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
    vector<vector<array<int, 4>>> ext(n, vector<array<int, 4>>(m));
    
    // LEFT & RIGHT
    for (int i = 0; i < n; ++i) {
        auto v = a[i];
        auto nxt = next_geq_val(v);
        auto prv = prev_geq_val(v);
        for (int j = 0; j < m; ++j) {
            ext[i][j][LEFT] = prv[j];
            ext[i][j][RIGHT] = nxt[j];
        }
    }
    // UP & DOWN
    for (int j = 0; j < m; ++j) {
        vector<int> v(n);
        for (int i = 0; i < n; ++i) v[i] = a[i][j];
        auto nxt = next_geq_val(v);
        auto prv = prev_geq_val(v);
        for (int i = 0; i < n; ++i) {
            ext[i][j][UP] = prv[i];
            ext[i][j][DOWN] = nxt[i];
        }
    }

    vector<SparseTable> strow(n);
    vector<SparseTable> stcol(m);
    for (int i = 0; i < n; ++i) {
        vector<int> v(m);
        for (int j = 0; j < m; ++j) {
            v[j] = ext[i][j][UP];
        }
        strow[i] = SparseTable(v);
    }
    for (int j = 0; j < m; ++j) {
        vector<int> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = ext[i][j][LEFT];
        }
        stcol[j] = SparseTable(v);
    }

    LL ans = 0;
    for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) {
        int rwall = m-1;
        for (int rr = r+2; rr < n; ++rr) {
            rwall = min(rwall, ext[rr-1][c][RIGHT]);
            int dwall = n-1;
            for (int cc = c+2; cc <= rwall; ++cc) {
                dwall = min(dwall, ext[r][cc-1][DOWN]);
                if (rr > dwall) break;
                bool works = true;
                // orizzontali
                works &= (strow[rr].query(c+1, cc) <= r);
/*
                for (int j = c+1; works && j < cc; ++j) {
                    // works &= (ext[r][j][DOWN] >= rr);
                    works &= (ext[rr][j][UP] <= r);
                }
*/
                // verticali
                works &= (stcol[cc].query(r+1, rr) <= c);
/*
                for (int i = r+1; works && i < rr; ++i) {
                    // works &= (ext[i][c][RIGHT] >= cc);
                    works &= (ext[i][cc][LEFT] <= c);
                }
*/
                ans += works;
            }
        }
    }

    return ans;
}

• 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