Submission #417726

#	Time	Username	Problem	Language	Result	Execution time	Memory
417726		usachevd0	Rectangles (IOI19_rect)	C++14	0 / 100	2 ms	588 KiB

rect

// #pragma gcc optimize("Ofast")
// #pragma gcc optimize("O3")
// #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,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 = 7e2 + 5;
bool badc[maxN];
int a[maxN][maxN];
int L[maxN], R[maxN];
int stk[maxN], sz;
int mxc[maxN];

// namespace fnw {
//     const int N = 7e2 + 5;
//     // int f[N][N];
    
//     // void add(int i0, int j0, int delta) {
//     //     for (int i = i0 + 1; i < N; i += i & -i)
//     //         for (int j = j0 + 1; j < N; j += j & -j)
//     //             f[i][j] += delta;
//     // }
//     // int gt(int i0, int j0) {
//     //     int res = 0;
//     //     for (int i = i0 + 1; i >= 1; i -= i & -i)
//     //         for (int j = j0 + 1; j >= 1; j -= j & -j)
//     //             res += f[i][j];
//     //     return res;
//     // }
    
//     int f[N];
    
//     void add(int i, int delta) {
//         for (++i; i < N; i += i & -i)
//             f[i] += delta;
//     }
//     int gt(int i) {
//         int res = 0;
//         for (++i; i >= 1; i -= i & -i)
//             res += f[i];
//         return res;
//     }
// }

int cl_sz[maxN], cl_head[maxN], cl_ord[maxN];

ll count_rectangles(vector<vector<int>> _a) {
    int n = _a.size(), m = _a[0].size();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            a[i][j] = _a[i][j];
    if (min(n, m) < 3) return 0;
    ll ans = 0;
    for (int r1 = 1; r1 < n - 1; ++r1) {
        for (int c = 0; c < m; ++c) {
            mxc[c] = -INF32;
            L[c] = 0;
            R[c] = m;
        }
        for (int r2 = r1; r2 < n - 1; ++r2) {
            badc[0] = badc[m - 1] = 1;
            for (int c = 1; c < m - 1; ++c) {
                chkmax(mxc[c], a[r2][c]);
                badc[c] = mxc[c] >= min(a[r1 - 1][c], a[r2 + 1][c]);
            }
            // count L
            sz = 0;
            for (int c = 0; c < m; ++c) {
                while (sz && a[r2][stk[sz - 1]] < a[r2][c])
                    --sz;
                if (sz)
                    chkmax(L[c], stk[sz - 1]);
                stk[sz++] = c;
            }
            // count R
            sz = 0;
            for (int c = m - 1; c >= 0; --c) {
                while (sz && a[r2][stk[sz - 1]] < a[r2][c])
                    --sz;
                if (sz)
                    chkmin(R[c], stk[sz - 1]);
                stk[sz++] = c;
            }
            
            fill(cl_sz, cl_sz + m, 0);
            for (int c = 0; c < m; ++c) {
                ++cl_sz[L[c]];
            }
            cl_head[m - 2] = 0;
            for (int c = m - 3; c >= 0; --c)
                cl_head[c] = cl_head[c + 1] + cl_sz[c + 1];
            for (int c = 0; c < m; ++c)
                cl_ord[cl_head[L[c]]++] = c;
            
            int b = m - 1;
            for (int c = m - 2; c >= 0; --c) {
                if (R[c] < m && R[c] <= b && R[c] >= c + 2) {
                    if (L[R[c]] < c)
                        ++ans;
                }
                for (int i = 0; i < cl_sz[c]; ++i) {
                    int d = cl_ord[cl_head[c] + i];
                    if (c + 2 <= d && d <= min(b, R[c]))
                        ++ans;
                }
                if (badc[c]) {
                    b = c;
                }
            }
            
            // int b = m - 1;
            // for (int c = m - 2; c >= 0; --c) {
            //     while (cl_sz[c + 1] > 0) {
            //         fnw::add(cl[c + 1][--cl_sz[c + 1]], -1);
            //     }
            //     ans += fnw::gt(min(b, R[c]));
            //     if (badc[c]) {
            //         b = c;
            //     }
            //     // add c + 1
            //     if (L[c + 1] <= c - 1) {
            //         cl[L[c + 1]][cl_sz[L[c + 1]]++] = c + 1;
            //         fnw::add(c + 1, +1);
            //     }
            // }
            // for (int c = 0; c <= m - 1; ++c)
            //     while (cl_sz[c] > 0)
            //         fnw::add(cl[c][--cl_sz[c]], -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