제출 #759226

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

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2525;
int n, m, U[N][N], D[N][N], L[N][N], R[N][N];
vector<pair<int, int>> ver[N], hor[N];
vector<pair<int, int>> my_ver[N][N];
vector<pair<int, int>> my_hor[N][N];

vector<pair<int, int>> clear_vec(vector<pair<int, int>> vec, int x, int y) {
    vector<pair<int, int>> new_vec;
    for (auto& p : vec) {
        if (abs(p.first - x) <= 1 || abs(p.second - y) <= 1) {
            continue;
        }
        new_vec.push_back(p);
    }
    return new_vec;
}

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

    // find U
    for (int j = 0; j < m; j++) {
        vector<int> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && a[i][j] > a[stk.back()][j]) {
                stk.pop_back();
            }
            U[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(i);
        }
    }

    // find D
    for (int j = 0; j < m; j++) {
        vector<int> stk;
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && a[i][j] > a[stk.back()][j]) {
                stk.pop_back();
            }
            D[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(i);
        }
    }

    // find L
    for (int i = 0; i < n; i++) {
        vector<int> stk;
        for (int j = 0; j < m; j++) {
            while (!stk.empty() && a[i][j] > a[i][stk.back()]) {
                stk.pop_back();
            }
            L[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(j);
        }
    }

    // find R
    for (int i = 0; i < n; i++) {
        vector<int> stk;
        for (int j = m - 1; j >= 0; j--) {
            while (!stk.empty() && a[i][j] > a[i][stk.back()]) {
                stk.pop_back();
            }
            R[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(j);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (R[i][j] != -1 && R[i][j] != j + 1)
                hor[j].emplace_back(R[i][j], i);

            if (L[i][j] != -1 && L[i][j] != j - 1)
                hor[L[i][j]].emplace_back(j, i);

            if (U[i][j] != -1 && U[i][j] != i - 1)
                ver[U[i][j]].emplace_back(i, j);

            if (D[i][j] != -1 && D[i][j] != i + 1)
                ver[i].emplace_back(D[i][j], j);
        }
    }

    for (int j = 0; j < m - 1; j++) {
        sort(hor[j].begin(), hor[j].end());
        hor[j].erase(unique(hor[j].begin(), hor[j].end()), hor[j].end());
        int sz = hor[j].size();
        for (int l = 0; l < sz; l++) {
            int r = l;
            while (r + 1 < sz && hor[j][r + 1].first == hor[j][l].first) r++;
            for (int x = l; x <= r; x++) {
                int y = x;
                while (y + 1 <= r && hor[j][y + 1].second == hor[j][y].second + 1) y++;
                for (int z = x; z <= y; z++) {
                    assert(hor[j][y].first > 0);
                    my_hor[hor[j][z].second][j + 1].emplace_back(hor[j][y].second, hor[j][y].first - 1); // format (i, j)
                }
//                if (hor[j][x].second > 0) {
//                    my_hor[hor[j][x].second - 1][j].emplace_back(min(n - 1, hor[j][y].second + 1), hor[j][y].first); // format (i, j)
//                }
                x = y;
            }
            l = r;
        }
    }

    for (int i = 0; i < n - 1; i++) {
        sort(ver[i].begin(), ver[i].end());
        ver[i].erase(unique(ver[i].begin(), ver[i].end()), ver[i].end());
        int sz = ver[i].size();
        for (int l = 0; l < sz; l++) {
            int r = l;
            while (r + 1 < sz && ver[i][r + 1].first == ver[i][l].first) r++;
            for (int x = l; x <= r; x++) {
                int y = x;
                while (y + 1 <= r && ver[i][y + 1].second == ver[i][y].second + 1) y++;
                for (int z = x; z <= y; z++) {
                    assert(ver[i][y].first > 0);
                    my_ver[i + 1][ver[i][z].second].emplace_back(ver[i][y].first - 1, ver[i][y].second); // format (i, j)
                }
//                if (ver[i][x].second > 0) {
//                    my_ver[i][ver[i][x].second - 1].emplace_back(ver[i][y].first, min(m - 1, ver[i][y].second + 1)); // format (i, j)
//                }
                x = y;
            }
            l = r;
        }
    }

//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            printf("(%d, %d): ", i, j);
//            for (auto& p : my_ver[i][j]) {
//                printf("[%d, %d] ", p.first, p.second);
//            }
//            printf("\n");
//        }
//    }
//
//    printf("\n");
//    printf("\n");
//    printf("\n");
//    printf("\n");
//    printf("\n");
//
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            printf("(%d, %d): ", i, j);
//            for (auto& p : my_hor[i][j]) {
//                printf("[%d, %d] ", p.first, p.second);
//            }
//            printf("\n");
//        }
//    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m - 1; j++) {
            sort(my_hor[i][j].begin(), my_hor[i][j].end());
//            my_hor[i][j] = clear_vec(my_hor[i][j], i, j);
            my_hor[i][j].erase(unique(my_hor[i][j].begin(), my_hor[i][j].end()), my_hor[i][j].end());


            sort(my_ver[i][j].begin(), my_ver[i][j].end());
//            my_ver[i][j] = clear_vec(my_ver[i][j], i, j);
            my_ver[i][j].erase(unique(my_ver[i][j].begin(), my_ver[i][j].end()), my_ver[i][j].end());
        }
    }

    auto is_valid = [&](int l1, int r1, int l2, int r2) {
        assert(l1 > 0 && l1 <= l2 && l2 < n - 1 && r1 > 0 && r1 <= r2 && r2 < m - 1);
        for (int i = l1; i <= l2; i++) {
            for (int j = r1; j <= r2; j++) {
                if (a[i][j] >= a[l1 - 1][j]) return false;
                if (a[i][j] >= a[l2 + 1][j]) return false;
                if (a[i][j] >= a[i][r1 - 1]) return false;
                if (a[i][j] >= a[i][r2 + 1]) return false;
            }
        }
        return true;
    };

    ll ans = 0;
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            vector<pair<int, int>> cells;
            for (auto& r : my_hor[i][j]) {
                for (auto& b : my_ver[i][j]) {
                    if (b.first <= r.first && b.second >= r.second) {
                        cells.emplace_back(b.first, r.second);
                    }
                }
            }
            sort(cells.begin(), cells.end());
            cells.erase(unique(cells.begin(), cells.end()), cells.end());
            for (auto& ff : cells) {
//                if (is_valid(i, j, ff.first, ff.second))
                    ans++;
            }
        }
    }


    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
*/

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:202:24: warning: unused variable 'ff' [-Wunused-variable]
  202 |             for (auto& ff : cells) {
      |                        ^~
rect.cpp:176:10: warning: variable 'is_valid' set but not used [-Wunused-but-set-variable]
  176 |     auto is_valid = [&](int l1, int r1, int l2, int r2) {
      |          ^~~~~~~~

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