Submission #417958

#	Time	Username	Problem	Language	Result	Execution time	Memory
417958		usachevd0	Rectangles (IOI19_rect)	C++17	0 / 100	744 ms	568488 KiB

rect

// #pragma gcc optimize("Ofast")
// #pragma gcc optimize("O3")
// #pragma gcc optimize("fast-math")
// #pragma gcc optimize("no-stack-protector")
// #pragma gcc optimize("unroll-loops")
// #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,sse4,sse5,popcnt")
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "rect.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int INF32 = 1e9;
const int maxN = 2503;
int n, m;
int a[maxN][maxN];
int U[maxN][maxN], D[maxN][maxN], L[maxN][maxN], R[maxN][maxN];
vector<int> goodH[maxN][maxN], goodV[maxN][maxN];
vector<int> goodVD[maxN][maxN];
int ptrVD[maxN][maxN];

int bh[maxN], bhc;
int bhl[maxN], bhr[maxN];

void precUDLR() {
    static int stk[maxN], sz;
    for (int y = 1; y <= m; ++y) {
        stk[0] = 0;
        sz = 1;
        for (int x = 1; x <= n; ++x) {
            while (a[stk[sz - 1]][y] < a[x][y])
                --sz;
            U[x][y] = stk[sz - 1];
            stk[sz++] = x;
        }
        stk[0] = n + 1;
        sz = 1;
        for (int x = n; x >= 1; --x) {
            while (a[stk[sz - 1]][y] < a[x][y])
                --sz;
            D[x][y] = stk[sz - 1];
            stk[sz++] = x;
        }
    }
    for (int x = 1; x <= n; ++x) {
        stk[0] = 0;
        sz = 1;
        for (int y = 1; y <= m; ++y) {
            while (a[x][stk[sz - 1]] < a[x][y])
                --sz;
            L[x][y] = stk[sz - 1];
            stk[sz++] = y;
        }
        stk[0] = m + 1;
        sz = 1;
        for (int y = m; y >= 1; --y) {
            while (a[x][stk[sz - 1]] < a[x][y])
                --sz;
            R[x][y] = stk[sz - 1];
            stk[sz++] = y;
        }
    }
}

ll count_rectangles(vector<vector<int>> _a) {
    n = _a.size(), m = _a[0].size();
    memset(a, 0x3f, sizeof a);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            a[i + 1][j + 1] = _a[i][j];
    precUDLR();
    for (int y = 1; y <= m; ++y)
        for (int x = 1; x <= n; ++x) {
            if (x + 2 <= D[x][y] && D[x][y] <= n) {
                goodH[x + 1][D[x][y] - 1].push_back(y);
                // debug("H", x, D[x][y], y);
            }
            if (1 <= U[x][y] && U[x][y] <= x - 2) {
                goodH[U[x][y] + 1][x - 1].push_back(y);
                // debug("H", U[x][y], x, y);
            }
        }
    for (int x = 1; x <= n; ++x) {
        for (int y = 1; y <= m; ++y) {
            if (y + 2 <= R[x][y] && R[x][y] <= m) {
                goodV[y + 1][R[x][y] - 1].push_back(x);
                // debug("V", y, R[x][y], x);
            }
            if (1 <= L[x][y] && L[x][y] <= y - 2) {
                goodV[L[x][y] + 1][y - 1].push_back(x);
                // debug("V", L[x][y], y, x);
            }
        }
    }
    for (int y1 = 2; y1 <= m - 1; ++y1)
        for (int y2 = y1; y2 <= m - 1; ++y2) {
            auto& g = goodV[y1][y2];
            if (g.empty()) continue;
            g.resize(unique(all(g)) - g.begin());
            auto& d = goodVD[y1][y2];
            int k = g.size();
            d.resize(k);
            d[k - 1] = g[k - 1];
            for (int i = k - 2; i >= 0; --i) {
                if (g[i + 1] == g[i] + 1)
                    d[i] = d[i + 1];
                else
                    d[i] = g[i];
            }
        }
    ll ans = 0;
    for (int r1 = 2; r1 <= n - 1; ++r1) {
        int* RR = R[r1];
        int* LL = L[r1];
        for (int r2 = r1; r2 <= n - 1; ++r2) {
            auto& gh = goodH[r1][r2];
            if (gh.empty()) continue;
            gh.resize(unique(all(gh)) - gh.begin());
            bhc = 0;           
            for (int c : gh) {
                if (c >= 2 && (!bhc || bh[bhc - 1] < c - 1))
                    bh[bhc++] = c - 1;
                if (!bhc || bh[bhc - 1] < c)
                    bh[bhc++] = c;
                if (c + 1 <= m && (!bhc || bh[bhc - 1] < c + 1))
                    bh[bhc++] = c + 1;
            }
            // debug(r1, r2);
            // debug(gh);
            // mdebug(bh, bhc);
            bhl[0] = bh[0];
            for (int i = 1; i < bhc; ++i) {
                if (bh[i - 1] == bh[i] - 1)
                    bhl[i] = bhl[i - 1];
                else
                    bhl[i] = bh[i];
            }
            bhr[bhc - 1] = bh[bhc - 1];
            for (int i = bhc - 2; i >= 0; --i) {
                if (bh[i + 1] == bh[i] + 1)
                    bhr[i] = bhr[i + 1];
                else
                    bhr[i] = bh[i];
            }
            // mdebug(bhl, bhc);
            // mdebug(bhr, bhc);
            for (int i = 0; i < bhc; ++i) {
                int c = bh[i];
                int l = LL[c];
                if (bhl[i] <= l && l <= c - 2 && RR[l] != c) {
                    // debug(l, c);
                    auto& gv = goodV[l + 1][c - 1];
                    auto& gvd = goodVD[l + 1][c - 1];
                    auto& ptr = ptrVD[l + 1][c - 1];
                    while (gv[ptr] != r1)
                        ++ptr;
                    ans += gvd[ptr] >= r2;
                    // if (gvd[ptr] >= r2) {
                    //     debug(r1, r2, l + 1, c - 1);
                    // }
                }
            }
            for (int i = 0; i < bhc; ++i) {
                int c = bh[i];
                int r = RR[c];
                if (c + 2 <= r && r <= bhr[i]) {
                    // debug(c, r);
                    auto& gv = goodV[c + 1][r - 1];
                    auto& gvd = goodVD[c + 1][r - 1];
                    auto& ptr = ptrVD[c + 1][r - 1];
                    while (gv[ptr] != r1)
                        ++ptr;
                    ans += gvd[ptr] >= r2;
                    // if (gvd[ptr] >= r2) {
                    //     debug(r1, r2, c + 1, r - 1);
                    // }
                }
            }
        }
    }
    return ans;
}

#ifdef LOCAL


int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    // InputReader inputReader(STDIN_FILENO);
    int n, m;
    cin >> n >> m;
    // n = inputReader.readInt();
    // m = inputReader.readInt();
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            // a[i][j] = inputReader.readInt();
        }
    }
    // inputReader.close();
    
    auto oldTime = Time;
    long long result = count_rectangles(a);
    debug(Time - oldTime);

    printf("%lld\n", result);
    fclose(stdout);
    return 0;
}
#endif

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