제출 #757809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757809		MilosMilutinovic	Rectangles (IOI19_rect)	C++14	10 / 100	909 ms	456140 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];

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 - 2; j++) {
        sort(hor[j].begin(), 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++) {
                    my_hor[hor[j][z].second][j].emplace_back(hor[j][y].second + 1, hor[j][y].first); // 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; i++) {
        sort(ver[i].begin(), 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++) {
                    my_ver[i][ver[i][z].second].emplace_back(ver[i][y].first, ver[i][y].second + 1); // 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 - 2; i++) {
        for (int j = 0; j < m - 2; j++) {
            sort(my_hor[i][j].begin(), my_hor[i][j].end());
            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].erase(unique(my_ver[i][j].begin(), my_ver[i][j].end()), my_ver[i][j].end());


        }
    }

    ll ans = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < m - 2; j++) {
            for (auto& r : my_hor[i][j]) {
                for (auto& b : my_ver[i][j]) {
                    if (b.first <= r.first && b.second >= r.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
*/

• 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