Submission #1214067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214067		thangdz2k7	Rectangles (IOI19_rect)	C++20	100 / 100	956 ms	177800 KiB

rect

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

using namespace std;

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

    vector <stack <int>> st_row(n - 1), st_col(m - 1);
    for (int i = 0; i < n - 1; ++ i) st_row[i].push(0);
    for (int j = 0; j < m - 1; ++ j) st_col[j].push(0);

    vector <vector <int>> cnt_row(m - 1, vector <int>(m - 1)), last_row(m - 1, vector <int>(m - 1)),
                          cnt_col(n - 1, vector <int>(n - 1)), last_col(n - 1, vector <int>(n - 1));

    vector <int> bit(n, 0);

    auto update = [&](int p, int val) -> void {
        for (; p < n; p += p & -p)
            bit[p] += val;
    };

    auto get = [&](int p) -> int {
        int ans = 0;
        for (; p; p -= p & -p)
            ans += bit[p];

        return ans;
    };

    long long ans = 0;

    for (int i = 0; i < n - 1; ++ i){
        for (int j = 0; j < m - 1; ++ j){
            bool ok = true;
            vector <pair <int, int>> rect_row, rect_col;

            while (!st_row[i].empty()){
                int pj = st_row[i].top();
                if (pj < j && ok){
                    if (last_row[pj + 1][j] < i - 1) cnt_row[pj + 1][j] = 0;
                    cnt_row[pj + 1][j] ++;
                    last_row[pj + 1][j] = i;
                    rect_row.emplace_back(j - pj, cnt_row[pj + 1][j]);
                }

                if (a[i][pj] > a[i][j + 1]) break;
                st_row[i].pop();
                ok &= a[i][pj] < a[i][j + 1];
            }
            st_row[i].push(j + 1);

            ok = true;
            while (!st_col[j].empty()){
                int pi = st_col[j].top();
                if (pi < i && ok){
                    if (last_col[pi + 1][i] < j - 1) cnt_col[pi + 1][i] = 0;
                    cnt_col[pi + 1][i] ++;
                    last_col[pi + 1][i] = j;
                    rect_col.emplace_back(cnt_col[pi + 1][i], i - pi);
                }

                if (a[pi][j] > a[i + 1][j]) break;
                st_col[j].pop();
                ok &= a[pi][j] < a[i + 1][j];
            }
            st_col[j].push(i + 1);

            sort(rect_col.rbegin(), rect_col.rend());
            reverse(rect_row.begin(), rect_row.end());
            int ptr = 0;

            for (auto [a, b] : rect_row){
                while (ptr < rect_col.size() && rect_col[ptr].first >= a) update(rect_col[ptr ++].second, 1);
                ans += get(b);
            }

            while (ptr --) update(rect_col[ptr].second, -1);
        }
    }

    return ans;
}

• 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