Submission #832154

#	Time	Username	Problem	Language	Result	Execution time	Memory
832154		maomao90	Rectangles (IOI19_rect)	C++17	100 / 100	3875 ms	950628 KiB

rect

// I can do all things through Christ who strengthens me
// Philippians 4:13

#include "rect.h"
#include "bits/stdc++.h"
using namespace std;

#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define SZ(x) (int) x.size()
#define ALL(x) x.begin(), x.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 2505;

int n, m;
vector<vi> a;
viii gdc, gdr;
vii mpr[MAXN][MAXN], mpc[MAXN][MAXN];
ll ans;

int fw[MAXN];
void incre(int i, int x) {
    i++;
    for (; i <= m; i += i & -i) {
        fw[i] += x;
    }
}
int qsm(int i) {
    i++;
    int res = 0;
    for (; i > 0; i -= i & -i) {
        res += fw[i];
    }
    return res;
}

ll count_rectangles(vector<vi> _a) {
    a = _a;
    n = SZ(a), m = SZ(a[0]);
    REP (j, 1, m - 1) {
        vi stk;
        REP (i, 0, n) {
            while (!stk.empty() && a[stk.back()][j] < a[i][j]) {
                stk.pop_back();
            }
            if (!stk.empty() && stk.back() + 1 <= i - 1) {
                gdc.pb({stk.back() + 1, i - 1, j});
            }
            stk.pb(i);
        }
        stk.clear();
        RREP (i, n - 1, 0) {
            while (!stk.empty() && a[stk.back()][j] < a[i][j]) {
                stk.pop_back();
            }
            if (!stk.empty() && i + 1 <= stk.back() - 1) {
                gdc.pb({i + 1, stk.back() - 1, j});
            }
            stk.pb(i);
        }
    }
    REP (i, 1, n - 1) {
        vi stk;
        REP (j, 0, m) {
            while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
                stk.pop_back();
            }
            if (!stk.empty() && stk.back() + 1 <= j - 1) {
                gdr.pb({stk.back() + 1, j - 1, i});
            }
            stk.pb(j);
        }
        stk.clear();
        RREP (j, m - 1, 0) {
            while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
                stk.pop_back();
            }
            if (!stk.empty() && j + 1 <= stk.back() - 1) {
                gdr.pb({j + 1, stk.back() - 1, i});
            }
            stk.pb(j);
        }
    }
    sort(ALL(gdc));
    gdc.erase(unique(ALL(gdc)), gdc.end());
    cerr << "GDC:\n";
    REP (i, 0, SZ(gdc)) {
        auto [s, e, c] = gdc[i];
        cerr << ' ' << s << ' ' << e << ' ' << c << '\n';
    }
    cerr << '\n';
    REP (i, 0, SZ(gdc)) {
        auto [s, e, c] = gdc[i];
        int ni = SZ(gdc) - 1;
        REP (j, i + 1, SZ(gdc)) {
            auto [ns, ne, nc] = gdc[j];
            if (s != ns || e != ne) {
                ni = j - 1;
                break;
            }
        }
        int pc = INF, mxc = INF;
        RREP (j, ni, i) {
            auto [ns, ne, nc] = gdc[j];
            if (nc + 1 != pc) {
                mxc = nc;
            }
            pc = nc;
            cerr << "   " << s << ' ' << nc << ": " << e << ' ' << mxc << '\n';
            mpc[s][nc].pb({e, mxc});
        }
        i = ni;
    }
    sort(ALL(gdr));
    gdr.erase(unique(ALL(gdr)), gdr.end());
    cerr << "GDR:\n";
    REP (i, 0, SZ(gdr)) {
        auto [s, e, c] = gdr[i];
        cerr << ' ' << s << ' ' << e << ' ' << c << '\n';
    }
    cerr << '\n';
    REP (i, 0, SZ(gdr)) {
        auto [s, e, r] = gdr[i];
        int ni = SZ(gdr) - 1;
        REP (j, i + 1, SZ(gdr)) {
            auto [ns, ne, nr] = gdr[j];
            if (s != ns || e != ne) {
                ni = j - 1;
                break;
            }
        }
        int pr = INF, mxr = INF;
        RREP (j, ni, i) {
            auto [ns, ne, nr] = gdr[j];
            if (nr + 1 != pr) {
                mxr = nr;
            }
            pr = nr;
            mpr[nr][s].pb({mxr, e});
        }
        i = ni;
    }
    REP (i, 1, n - 1) {
        REP (j, 1, m - 1) {
            sort(ALL(mpc[i][j]), greater<ii>());
            sort(ALL(mpr[i][j]), greater<ii>());
            int ptr = 0;
            cerr << i << ' ' << j << '\n';
            for (auto [h, w] : mpc[i][j]) {
                while (ptr < SZ(mpr[i][j]) && mpr[i][j][ptr].FI >= h) {
                    cerr << "  + " << mpr[i][j][ptr].FI << ' ' << mpr[i][j][ptr].SE << '\n';
                    incre(mpr[i][j][ptr++].SE, 1);
                }
                int tmp = qsm(w);
                cerr << "  ? " << h << ' ' << w << ": " << tmp << '\n';
                ans += tmp;
            }
            while (ptr > 0) {
                incre(mpr[i][j][--ptr].SE, -1);
            }
        }
    }
    /*
    REP (i, 1, n - 1) {
        REP (j, 1, m - 1) {
            REP (k, i, n - 1) {
                REP (l, j, m - 1) {
                    if (!gdc[i][l][k]) {
                        break;
                    }
                    bool pos = 1;
                    REP (p, i, k + 1) {
                        if (!gdr[p][j][l]) {
                            pos = 0;
                            break;
                        }
                    }
                    ans += pos;
                }
            }
        }
    }
    assert(ans <= n * m);
    */
    return ans;
}

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