Submission #561099

#	Time	Username	Problem	Language	Result	Execution time	Memory
561099		hoanghq2004	Rectangles (IOI19_rect)	C++14	59 / 100	946 ms	34856 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];
int vis[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

long long count_rectangles(vector <vector <int>> a) {
    int n = a.size();
    int m = a[0].size();
    if (n * m > 5e5) {
        long long ans = 0;
        auto bfs = [&](int x, int y) {
            queue <pair <int, int> > q;
            q.push({x, y});
            int up = x, down = x, lft = y, rgt = y;
            int cnt = 0;
            while (q.size()) {
                auto [u, v] = q.front();
                q.pop();
                ++cnt;
                up = min(up, u);
                down = max(down, u);
                lft = min(lft, v);
                rgt = max(rgt, v);
                for (int i = 0; i < 4; ++i) {
                    int x = u + dx[i];
                    int y = v + dy[i];
                    if (x < 0 || x >= n || y < 0 || y >= m || a[x][y] || vis[x][y]) continue;
                    vis[x][y] = 1;
                    q.push({x, y});
                }
            }
            if (lft > 0 && rgt < m - 1 && up > 0 && down < n - 1 && cnt == (rgt - lft + 1) * (down - up + 1)) ++ans;
        };
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (vis[i][j] == 0 && a[i][j] == 0) bfs(i, j);
        return ans;
    }
    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 lambda function:
rect.cpp:33:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |                 auto [u, v] = q.front();
      |                      ^
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:121:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             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