제출 #500407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500407		MilosMilutinovic	Rectangles (IOI19_rect)	C++14	37 / 100	5077 ms	394460 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2505;

const pair<int, int> neg = make_pair(-1, -1);

int n, m;
int a[N][N];
pair<int, int> L[N][N];
pair<int, int> R[N][N];
pair<int, int> D[N][N];
pair<int, int> U[N][N];

ll count_rectangles(vector<vector<int>> A) {
    n = A.size();
    m = A[0].size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = A[i][j];
            L[i][j] = neg;
            R[i][j] = neg;
            U[i][j] = neg;
            D[i][j] = neg;
        }
    }
    vector<tuple<int, int, int, int>> good;
    for (int i = 0; i < n; i++) {
        stack<pair<int, int>> stk;
        for (int j = 0; j < m; j++) {
            while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
                stk.pop();
            }
            if (!stk.empty()) {
                L[i][j] = stk.top();
                good.emplace_back(stk.top().first, stk.top().second, i, j);
            }
            stk.push({i, j});
        }
    }
    for (int i = 0; i < n; i++) {
        stack<pair<int, int>> stk;
        for (int j = m - 1; j >= 0; j--) {
            while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
                stk.pop();
            }
            if (!stk.empty()) {
                R[i][j] = stk.top();
                good.emplace_back(i, j, stk.top().first, stk.top().second);
            }
            stk.push({i, j});
        }
    }
    for (int j = 0; j < m; j++) {
        stack<pair<int, int>> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
                stk.pop();
            }
            if (!stk.empty()) {
                U[i][j] = stk.top();
                good.emplace_back(stk.top().first, stk.top().second, i, j);
            }
            stk.push({i, j});
        }
    }
    for (int j = 0; j < m; j++) {
        stack<pair<int, int>> stk;
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
                stk.pop();
            }
            if (!stk.empty()) {
                D[i][j] = stk.top();
                good.emplace_back(i, j, stk.top().first, stk.top().second);
            }
            stk.push({i, j});
        }
    }
    /*cout << "L:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << L[i][j].first << " " << L[i][j].second << "    ";
        }
        cout << "\n";
        cout << "\n";
    }*/
    //cout << D[1][1].first << " " << D[1][1].second << "\n";
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int cnt_my = 0;
            for (int len = 1; len < i; len++) {
                for (int x = 1; x < j; x++) {
                    bool ok = true;
                    for (int c = 1; c <= x && ok; c++) {
                        pair<int, int> my = {i, j - c};
                        pair<int, int> his = {i - len - 1, j - c};
                        if ((U[my.first][my.second] != neg && U[my.first][my.second].first > his.first) || (D[his.first][his.second] != neg && D[his.first][his.second].first < my.first)) {
                            ok = false;
                        }
                    }
                    for (int c = 1; c <= len && ok; c++) {
                        pair<int, int> my = {i - c, j};
                        pair<int, int> his = {i - c, j - x - 1};
                        if ((L[my.first][my.second] != neg && L[my.first][my.second].second > his.second) || (R[his.first][his.second] != neg && R[his.first][his.second].second < my.second)) {
                            ok = false;
                        }
                    }
                    ans += ok;
                    cnt_my += ok;
                    /*if (ok) {
                        cout << i - len + 1 << " " << j - x + 1 << " " << i << " " << j << endl;
                    }*/
                }
            }
            //assert(cnt_my <= 100);
        }
    }
    return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/

• 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