Submission #561081

#	Time	Username	Problem	Language	Result	Execution time	Memory
561081		hoanghq2004	Rectangles (IOI19_rect)	C++14	59 / 100	5077 ms	71796 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];
int L[N], R[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 solve = [&](int from, int to) {
        int ans = 0;
        for (int i = from; i <= to; ++i)
            for (int j = i; j <= to; ++j)
                if (R[i - 1] >= j && L[j + 1] <= i) ++ans;
        return ans;
    };
    long long ans = 0;
    for (int top = 1; top < n - 1; ++top) {
        for (int i = 0; i < m; ++i) L[i] = 0, R[i] = m;
        for (int bot = top; bot < n - 1; ++bot) {
            for (int i = 0; i < m; ++i) L[i] = max(L[i], lft[bot][i]), R[i] = min(R[i], rgt[bot][i]);
            vector <int> s = {0};
            for (int i = 1; i < m - 1; ++i)
                if (down[top - 1][i] < bot || up[bot + 1][i] > top) s.push_back(i);
            s.push_back(m - 1);
            for (int i = 1; i < s.size(); ++i) {
                if (s[i] != s[i - 1] + 1) ans += solve(s[i - 1] + 1, s[i] - 1);
            }
        }
    }
    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';
//}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:88:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for (int i = 1; i < s.size(); ++i) {
      |                             ~~^~~~~~~~~~

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