Submission #412291

#	Time	Username	Problem	Language	Result	Execution time	Memory
412291		timmyfeng	Rectangles (IOI19_rect)	C++17	0 / 100	834 ms	1048580 KiB

rect

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

#include <bits/extc++.h>

template <class T, class Comp = less<T>>
using ordered_set = __gnu_pbds::tree<
    T, __gnu_pbds::null_type, Comp,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update
>;

const int N = 2500;

ordered_set<int> where_h[N][N], where_v[N][N];
vector<int> jump_h[N][N], jump_v[N][N];

bool check(ordered_set<int> &s, int a, int b) {
    return (int) (s.order_of_key(b + 1) - s.order_of_key(a)) == b - a + 1;
}

long long count_rectangles(vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();

    for (int i = 0; i < n; ++i) {
        vector<int> mono;
        for (int j = 0; j < m; ++j) {
            while (!mono.empty() && a[i][mono.back()] <= a[i][j]) {
                jump_h[i][mono.back() + 1].push_back(j - 1);
                where_h[mono.back() + 1][j - 1].insert(i);
                mono.pop_back();
            }

            if (!mono.empty()) {
                jump_h[i][mono.back() + 1].push_back(j - 1);
                where_h[mono.back() + 1][j - 1].insert(i);
            }

            mono.push_back(j);
        }
    }

    for (int i = 0; i < m; ++i) {
        vector<int> mono;
        for (int j = 0; j < n; ++j) {
            while (!mono.empty() && a[mono.back()][i] <= a[j][i]) {
                jump_v[mono.back() + 1][i].push_back(j - 1);
                where_v[mono.back() + 1][j - 1].insert(i);
                mono.pop_back();
            }

            if (!mono.empty()) {
                jump_v[mono.back() + 1][i].push_back(j - 1);
                where_v[mono.back() + 1][j - 1].insert(i);
            }

            mono.push_back(j);
        }
    }

    int ans = 0;
    for (int i1 = 0; i1 < n; ++i1) {
        for (int j1 = 0; j1 < m; ++j1) {
            for (auto i2 : jump_v[i1][j1]) {
                for (auto j2 : jump_h[i1][j1]) {
                    if (i1 <= i2 && j1 <= j2) {
                        ans += check(where_v[i1][i2], j1, j2) && check(where_h[j1][j2], i1, i2);
                    }
                }
            }
        }
    }

    return ans;
}

• 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