Submission #1346827

#TimeUsernameProblemLanguageResultExecution timeMemory
1346827kawhietLuxury burrow (IZhO13_burrow)C++20
100 / 100
1070 ms12316 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

int get(vector<int> h) {
    int n = h.size();
    vector<int> l(n, -1), r(n, n), stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && h[stk.back()] >= h[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            l[i] = stk.back();
        }
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && h[stk.back()] >= h[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            r[i] = stk.back();
        }
        stk.push_back(i);
    }
    int ret = 0;
    for (int i = 0; i < n; i++) {
        ret = max(ret, h[i] * (r[i] - l[i] - 1));
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    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];
        }
    }
    int l = 0, r = 2e9, ans = 0;
    while (l + 1 < r) {
        int tm = (l + r) / 2;
        vector<vector<int>> b(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                b[i][j] = (a[i][j] >= tm);
            }
        }
        vector<vector<int>> p(n, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j + 1] = p[i][j] + b[i][j];
            }
        }
        int mx = 0;
        for (int j = 0; j < m; j++) {
            vector<int> h;
            for (int i = 0; i < n; i++) {
                int tl = 0, tr = m + 1;
                while (tl + 1 < tr) {
                    int mid = (tl + tr) / 2;
                    if (j + mid > m) {
                        tr = mid;
                        continue;
                    }
                    if (p[i][j + mid] - p[i][j] == mid) {
                        tl = mid;
                    } else {
                        tr = mid;
                    }
                }
                h.push_back(tl);
            }
            mx = max(mx, get(h));
        }
        if (mx >= k) {
            ans = mx;
            l = tm;
        } else {
            r = tm;
        }
    }
    cout << l << ' ' << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...