Submission #1107077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107077		underwaterkillerwhale	Rectangles (IOI19_rect)	C++17	72 / 100	1215 ms	260508 KiB

rect

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 4e3 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 1e9 + 7;
const int BASE = 137;
const int szBL = 350;

int n, m;
int a[N][N];

namespace sub5 {
    ll solution() {
        vector<vector<int>> toD(n + 1, vector<int> (m + 1, 0)),
                        toU(n + 1, vector<int> (m + 1, 0)); ///hàng

        rep (j, 1, m) {
            stack<pii> st;
            rep (i, 1, n) {
                while (!st.empty() && st.top().fs < a[i][j]) st.pop();
                if (!st.empty()) toU[i][j] = st.top().se + 1;
                else toU[i][j] = 1;
                st.push({a[i][j], i});
            }

            stack<pii> ().swap(st);
            reb (i, n, 1) {
                while (!st.empty() && st.top().fs < a[i][j]) st.pop();
                if (!st.empty()) toD[i][j] = st.top().se - 1;
                else toD[i][j] = n;
                st.push({a[i][j], i});
            }
        }

        int res = 0;

        vector<int> mxR(n + 3, 0), Down(n + 3, n), Up(n + 3, 1);
        rep (j, 1, m) {
            rep (i, 1, n)
                mxR[i] = 0, Down[i] = n, Up[i] = 1;

            reb (k, j - 1, 1) {
                int bound = n;
                reb (i, n, 1) {
                    if (Down[i] < bound && Down[i] > i) {
                        if (Up[Down[i] + 1] <= i + 1) {
                            ++res;
                        }
                    }
                    if (mxR[i] >= min(a[i][j], a[i][k])) {
                        bound = i;
                    }
                }
                bound = 1;
                rep (i, 1, n) {
                    if (Up[i] > bound && Up[i] < i) {
//                        cout << j <<" "<<k<<" "<<i<<" "<<Up[i] - 1  <<" dasaa\n";
                        if (Down[Up[i] - 1] >= i) {
                            ++res;
                        }
                    }
                    if (mxR[i] >= min(a[i][j], a[i][k])) {
                        bound = i;
                    }
                }
                ///update
                rep (i, 1, n) {
                    mxR[i] = max(mxR[i], a[i][k]);
                    Down[i] = min(Down[i], toD[i][k]);
                    Up[i] = max(Up[i], toU[i][k]);
                }
            }
        }
        return res;
//        cout << res <<"\n";
    }
}

namespace sub6 {
    bool check () {
        rep (i, 1, n)
        rep (j, 1, m) if (a[i][j] > 1) return 0;
        return 1;
    }
    ///prefix sum
    int solution() {
        vector<vector<int>> Up(n + 3, vector<int> (m + 3, 0)),
                            Left (n + 3, vector<int> (m + 3, 0)),
                            nearbyC(n + 3, vector<int> (m + 3, -1)),///doc
                            nearbyR(n + 3, vector<int> (m + 3, -1)),///ngang
                            pre(n + 3, vector<int> (m + 3, 0));
        rep (i, 1, n) {
            rep (j, 1, m) {
                Up[i][j] = a[i - 1][j] == 0 ? i : Up[i - 1][j];
                Left[i][j] = a[i][j - 1] == 0 ? j : Left[i][j - 1];
            }
        }
        rep (i, 1, n)
        rep (j, 1, m) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];

        auto getSum = [&] (int x, int y, int u, int v) ->int {
            if (x > u || y > v ) return -1;
            return pre[u][v] - pre[u][y - 1] - pre[x - 1][v] + pre[x - 1][y - 1];
        };

        int res = 0;
        rep (i, 1, n) {
            rep (j, 1, m) {
                if (nearbyR[i][j - 1] >= Left[i][j] - 1 && nearbyC[i - 1][j] >= Up[i][j] - 1) {
                    int u = i, v = j, x = nearbyC[i - 1][j], y = nearbyR[i][j - 1];
//                    cout << i <<","<<j<<" "<<nearbyC[i - 1][j] <<" "<<nearbyR[i][j - 1]<<" "<<(u - x - 1) * 2 + (v - y + 1) * 2<<"\n";
                    if (getSum(x + 1, y + 1, u - 1, v - 1) == 0 && getSum(x, y, u, v) - a[u][v] - a[x][v] - a[u][y] - a[x][y] == (u - x - 1) * 2 + (v - y + 1) * 2 - 4) {
                        ++res;
                    }
                }
                nearbyR[i][j] = (a[i - 1][j] == 1) ? j : nearbyR[i][j - 1];
                nearbyC[i][j] = (a[i][j - 1] == 1) ? i : nearbyC[i - 1][j];
            }
        }
//        cout << res <<"\n";
        return res;
    }
}

ll count_rectangles (vector<vector<int>> A) {
    n = SZ(A);
    m = SZ(A[0]);
    rep (i, 1, n)
    rep (j, 1, m) a[i][j] = A[i - 1][j - 1];
    if (n * m <= 490000)
        return sub5 :: solution();
    else if (sub6 :: check())
        return sub6 :: solution();

}

void solution () {
//    cout << count_rectangles({{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}});
//    return;
    cin >> n >> m;
    rep (i, 1, n)
    rep (j, 1, m) cin >> a[i][j];
//    if (n * m <= 490000)
//        cout << sub5 :: solution() <<"\n";
    cout << sub6 :: solution() <<"\n";
}

//#define file(name) freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
//main () {
//    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +20
gọi sao cho có lợi cho mình nhất
*/

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:153:1: warning: control reaches end of non-void function [-Wreturn-type]
  153 | }
      | ^

• 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