Submission #412471

#	Time	Username	Problem	Language	Result	Execution time	Memory
412471		timmyfeng	Rectangles (IOI19_rect)	C++17	72 / 100	5100 ms	1027812 KiB

rect

#include <bits/stdc++.h>
using namespace std;

const int N = 2500;

map<int, int> where_h[N][N], where_v[N][N];
int jump_h[N][N][2], jump_v[N][N][2];

array<int, 4> rects[8 * N * N];

void update(map<int, int> &s, int a) {
    int l = a;
    auto nxt = s.upper_bound(a);
    if (nxt != s.begin()) {
        auto prv = nxt; --prv;
        if (prv->second + 1 == a) {
            l = prv->first;
        }
    }

    int r = a;
    if (nxt != s.end() && nxt->first - 1 == a) {
        r = nxt->second;
        s.erase(nxt);
    }

    s[l] = r;
}

bool query(map<int, int> &s, int a, int b) {
    auto it = s.upper_bound(a);
    return it != s.begin() && (--it)->second >= b;
}

long long 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) {
            for (int k = 0; k < 2; ++k) {
                jump_h[i][j][0] = jump_v[i][j][0] = -1;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        vector<int> mono;
        for (int j = 0; j < m; ++j) {
            bool equal = false;
            while (!mono.empty() && a[i][mono.back()] <= a[i][j]) {
                int k = mono.back();
                mono.pop_back();
                equal = a[i][k] == a[i][j];
                if (k + 1 <= j - 1) {
                    update(where_h[k + 1][j - 1], i);
                    jump_h[i][k + 1][1] = j - 1;
                }
            }

            if (!mono.empty() && !equal) {
                int k = mono.back();
                if (k + 1 <= j - 1) {
                    update(where_h[k + 1][j - 1], i);
                    jump_h[i][j - 1][0] = k + 1;
                }
            }

            mono.push_back(j);
        }
    }

    for (int i = 0; i < m; ++i) {
        vector<int> mono;
        for (int j = 0; j < n; ++j) {
            bool equal = false;
            while (!mono.empty() && a[mono.back()][i] <= a[j][i]) {
                int k = mono.back();
                mono.pop_back();
                equal = a[k][i] == a[j][i];
                if (k + 1 <= j - 1) {
                    update(where_v[k + 1][j - 1], i);
                    jump_v[k + 1][i][1] = j - 1;
                }
            }

            if (!mono.empty() && !equal) {
                int k = mono.back();
                if (k + 1 <= j - 1) {
                    update(where_v[k + 1][j - 1], i);
                    jump_v[j - 1][i][0] = k + 1;
                }
            }

            mono.push_back(j);
        }
    }

    int ans = 0;
    for (int a = 0; a < n; ++a) {
        for (int b = 0; b < m; ++b) {
            for (auto c : jump_v[a][b]) {
                if (c != -1) {
                    for (auto d : {a, c}) {
                        for (auto e : jump_h[d][b]) {
                            if (e != -1) {
                                int w = min(a, c), x = max(a, c);
                                int y = min(b, e), z = max(b, e);
                                if (query(where_v[w][x], y, z) && query(where_h[y][z], w, x)) {
                                    rects[ans++] = {w, x, y, z};
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    sort(rects, rects + ans);

    return unique(rects, rects + ans) - rects;
}

• 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: 0 / 28