Submission #561131

#	Time	Username	Problem	Language	Result	Execution time	Memory
561131		hoanghq2004	Rectangles (IOI19_rect)	C++14	37 / 100	5089 ms	73404 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rect.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2510;

int up[N][N], down[N][N], lft[N][N], rgt[N][N];

long long count_rectangles(vector <vector <int>> a) {
    int n = a.size();
    int m = a[0].size();
    for (int i = 0; i < n; ++i) {
        stack <int> stk;
        for (int j = 0; j < m; ++j) {
            while (stk.size() && a[i][j] >= a[i][stk.top()]) {
                rgt[i][stk.top()] = j - 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            rgt[i][stk.top()] = m - 1;
            stk.pop();
        }
        for (int j = m - 1; j >= 0; --j) {
            while (stk.size() && a[i][j] >= a[i][stk.top()]) {
                lft[i][stk.top()] = j + 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            lft[i][stk.top()] = 0;
            stk.pop();
        }
    }
    for (int i = 0; i < m; ++i) {
        stack <int> stk;
        for (int j = 0; j < n; ++j) {
            while (stk.size() && a[j][i] >= a[stk.top()][i]) {
                down[stk.top()][i] = j - 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            down[stk.top()][i] = n - 1;
            stk.pop();
        }
        for (int j = n - 1; j >= 0; --j) {
            while (stk.size() && a[j][i] >= a[stk.top()][i]) {
                up[stk.top()][i] = j + 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            up[stk.top()][i] = 0;
            stk.pop();
        }
    }
    auto check = [&](int x, int y, int u, int v) {
        for (int i = x; i <= u; ++i)
            if (rgt[i][y - 1] < v || lft[i][v + 1] > y) return 0;
        for (int i = y; i <= v; ++i)
            if (down[x - 1][i] < u || up[u + 1][i] > x) return 0;
        for (int i = x; i <= u; ++i)
            assert(rgt[i][y - 1] == v || lft[i][v + 1] == y);
        for (int i = y; i <= v; ++i)
            assert(down[x - 1][i] == u || up[u + 1][i] == x);
        return 1;
    };
    long long ans = 0;
    for (int x = 1; x < n - 1; ++x)
        for (int y = 1; y < m - 1; ++y)
            for (int u = x; u < n - 1; ++u)
                for (int v = y; v < m - 1; ++v)
                    ans += check(x, y, u, v);
    return ans;
}
//
//int main() {
//	int n, m;
//    cin >> n >> m;
//	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];
//		}
//	}
//	cout << count_rectangles(a) << '\n';
//}

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