Submission #1106765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106765		underwaterkillerwhale	Rectangles (IOI19_rect)	C++17	59 / 100	5076 ms	71372 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";
    }
}

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];
    return sub5 :: 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) sub5 :: solution();
}

//#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 +15
gọi sao cho có lợi cho mình nhất
*/

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