Submission #439340

#	Time	Username	Problem	Language	Result	Execution time	Memory
439340		Sorting	Rectangles (IOI19_rect)	C++17	10 / 100	5061 ms	22792 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;
typedef long long ll;

const int N = 2500 + 3;

vector<vector<int>> a;
int n, m;
pair<int, int> imp[N][N];

bool check(int x1, int y1, int x2, int y2){
    for(int i = x1; i <= x2; ++i)
        for(int j = y1; j <= y2; ++j)
            if(a[i][j] >= a[x1 - 1][j] || a[i][j] >= a[x2 + 1][j] || a[i][j] >= a[i][y1 - 1] || a[i][j] >= a[i][y2 + 1])
                return false;
    return true; 
}

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

    ll ans = 0;
    for(int x1 = 1; x1 < n - 1; ++x1)
        for(int y1 = 1; y1 < m - 1; ++y1){
            pair<int, int> mx{x1, y1};
            int x_lim = n - 2, y_lim = m - 2;
            if(imp[x1][y1].first){
                x_lim = imp[x1][y1].first;
                y_lim = imp[x1][y1].second;
            }
            for(int x2 = x1; x2 <= x_lim; ++x2)
                for(int y2 = y1; y2 <= y_lim; ++y2){
                    bool b = check(x1, y1, x2, y2);
                    ans += b;
                    if(b) mx = max(mx, {x2, y2});
                }
            for(int x2 = x1; x2 <= mx.first; ++x2)
                for(int y2 = y1; y2 <= mx.second; ++y2)
                    imp[x2][y2] = mx;
        }
    return ans;
}

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