Submission #1068022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068022		becaido	Rectangles (IOI19_rect)	C++17	72 / 100	5070 ms	218644 KiB

rect

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "rect.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
const int SIZE = 2505;

int n, m;
ll ans;
int a[SIZE][SIZE];
int U[SIZE][SIZE], D[SIZE][SIZE];
int L[SIZE][SIZE], R[SIZE][SIZE];

ll n_small() {
    if (n < 3) return 0;
    FOR (l, 2, m - 1) {
        int mx = 0;
        FOR (r, l, m - 1) {
            if (a[2][r] >= min(a[1][r], a[3][r])) break;
            mx = max(mx, a[2][r]);
            ans += (mx < min(a[2][l - 1], a[2][r + 1]));
        }
    }
    return ans;
}

ll a_small() {
    FOR (i, 1, n) FOR (j, 1, m) if (a[i][j] == 0) {
        queue<pair<int, int>> q;
        q.emplace(i, j), a[i][j] = -1;
        int u = n + 1, d = 0, l = m + 1, r = 0, cnt = 0;
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            cnt++;
            u = min(u, x), d = max(d, x);
            l = min(l, y), r = max(r, y);
            FOR (k, 0, 3) {
                int tx = x + dx[k], ty = y + dy[k];
                if (1 <= tx && tx <= n && 1 <= ty && ty <= m && a[tx][ty] == 0) {
                    q.emplace(tx, ty);
                    a[tx][ty] = -1;
                }
            }
        }
        if (1 < u && d < n && 1 < l && r < m && cnt == (d - u + 1) * (r - l + 1)) ans++;
    }
    return ans;
}

int bit[SIZE];
void upd(int pos, int x) {
    for (; pos <= m; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}
int que(int l, int r) {
    return l > r ? 0 : que(r) - que(l - 1);
}

int curL[SIZE], curR[SIZE], cnt[SIZE];
ll count_rectangles(vector<vector<int>> _a) {
    n = _a.size(), m = _a[0].size(), ans = 0;
    FOR (i, 1, n) FOR (j, 1, m) a[i][j] = _a[i - 1][j - 1];
    if (n <= 3) return n_small();

    {
        int mx = 0;
        FOR (i, 1, n) mx = max(mx, *max_element(a[i] + 1, a[i] + m + 1));
        if (mx <= 1) return a_small();
    }

    FOR (i, 1, n) {
        vector<int> st;
        FOR (j, 1, m) {
            while (st.size() && a[i][j] > a[i][st.back()]) st.pop_back();
            L[i][j] = (st.size() ? st.back() + 1 : 1);
            st.pb(j);
        }
        st.clear();
        for (int j = m; j >= 1; j--) {
            while (st.size() && a[i][j] > a[i][st.back()]) st.pop_back();
            R[i][j] = (st.size() ? st.back() - 1 : m);
            st.pb(j);
        }
    }
    FOR (j, 1, m) {
        vector<int> st;
        FOR (i, 1, n) {
            while (st.size() && a[i][j] > a[st.back()][j]) st.pop_back();
            U[i][j] = (st.size() ? st.back() + 1 : 1);
            st.pb(i);
        }
        st.clear();
        for (int i = n; i >= 1; i--) {
            while (st.size() && a[i][j] > a[st.back()][j]) st.pop_back();
            D[i][j] = (st.size() ? st.back() - 1 : n);
            st.pb(i);
        }
    }

    FOR (u, 2, n - 1) {
        fill(curL + 1, curL + m + 1, 0);
        fill(curR + 1, curR + m + 1, m + 1);
        FOR (d, u, n - 1) {
            FOR (j, 1, m) {
                curL[j] = max(curL[j], L[d][j]);
                curR[j] = min(curR[j], R[d][j]);
            }

            auto cal = [&](int l, int r) {
                vector<pair<int, int>> all;
                FOR (j, l, r) all.pb(max(l, curL[j + 1]), j);
                sort(all.begin(), all.end());
                int p = 0;
                FOR (j, l, r) {
                    while (p < all.size() && all[p].F <= j) upd(all[p].S, 1), p++;
                    ans += que(j, curR[j - 1]);
                }
                while (p > 0) {
                    p--;
                    upd(all[p].S, -1);
                }
            };

            int l = 0;
            FOR (j, 2, m - 1) if (D[u - 1][j] >= d && U[d + 1][j] <= u) {
                if (l == 0) l = j;
                if (j == m - 1 || !(D[u - 1][j + 1] >= d && U[d + 1][j + 1] <= u)) {
                    int r = j;
                    cal(l, r);
                    l = 0;
                }
            }
        }
    }
    return ans;
}

/*
in1
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
out1
6

5 5
0 1 1 1 0
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
0 1 1 1 0
*/

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:144:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |                     while (p < all.size() && all[p].F <= j) upd(all[p].S, 1), p++;
      |                            ~~^~~~~~~~~~~~

• 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: 0 / 28