Submission #1216416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216416		jasonic	Rectangles (IOI19_rect)	C++20	59 / 100	2287 ms	1114112 KiB

rect

/*

lemma 1: if we calculate the first value each cell sees to the left/right/up/down direction, these are the only valid rectangles
proof: consider a rectangle where all l/r/u/d bounds are incorrect for some direction for every cell. WLOG, let v be the biggest element in the rectangle. then, it follows that since this value is incorrect for some value. WLOG, let this incorrect value be towards the right, and its x-value be xb. it implies one of two cases:
- the right bound of the rectangle is to the left of xb: thus, since xb is the first value to the right where v is less than the value at xb, that means that the boundary has a smaller value at that row. contradiction
- the right bound of the rectangle is to the right of xb: this contradicts the fact that v is the biggest element since xb is in the range. contradiction.

corollary 1.1: for each rectangle, each row and column's maximum should be satisfied by at least one value.


so now we have Omega(nm) rectangles to check, do it in O(fast)?


lemma 2: for each value on the boundary of the rectangle, we must have that the first value greater than it to the direction towards the center of the rectangle should be outside of the rectangle.

proof: take the max value of the row/column inside of the rectangle adjacent to the cell on the boundary. look at the minimum bounds of that cell with respect to the row/column depending on the boundary cell we chose. since this is a valid rectangle, then it implies that there isnt a bigger element inside the rectangle.

therefore we can do four range queries on the boundaries to see if it goes over the bounds.

*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

struct MinMaxST{
    int l, r;
    MinMaxST *lt, *rt;
    int mn, mx;

    void comb() {
        mn = min(lt->mn, rt->mn);
        mx = max(lt->mx, rt->mx);
    }

    // first value is the one thats on min, the second is the one thats on max
    MinMaxST(int bl, int br, vector<int> &a, vector<int> &b) {
        lt = rt = nullptr;
        l = bl, r = br;

        if(l == r) {
            mn = a[l];
            mx = b[l];
        } else {
            int m = (l+r)/2;
            lt = new MinMaxST(l, m, a, b);
            rt = new MinMaxST(m+1, r, a, b);
            comb();
        }
    }

    int qryMin(int ql, int qr) {
        if(qr < l || r < ql) return 7'000'005;
        if(ql <= l && r <= qr) return mn;
        else return min(lt->qryMin(ql, qr), rt->qryMin(ql, qr));
    }

    int qryMax(int ql, int qr) {
        if(qr < l || r < ql) return -1;
        if(ql <= l && r <= qr) return mx;
        else return max(lt->qryMax(ql, qr), rt->qryMax(ql, qr));
    }
};

ll count_rectangles(vector<vector<int>> arr) {
    int r = size(arr);
    int c = size(arr[0]);
    
    vector<vector<int>> maxUp(r, vector<int>(c, -1));
    vector<vector<int>> maxDown(r, vector<int>(c, r));

    // flipped so that its easy to turn into a segment tree
    vector<vector<int>> maxLeft(c, vector<int>(r, -1));
    vector<vector<int>> maxRight(c, vector<int>(r, c));

    set<tuple<int, int, int, int>> valid;

    // process first left
    for(int y = 0; y < r; y++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(int x = 0; x < c; x++) {
            while(maxStack.top().first <= arr[y][x]) maxStack.pop();
            maxLeft[x][y] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], x));
        }
    }

    // process first right
    for(int y = 0; y < r; y++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, c));
        for(int x = c-1; x >= 0; x--) {
            while(maxStack.top().first <= arr[y][x]) maxStack.pop();
            maxRight[x][y] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], x));
        }
    }

    for(int x = 0; x < c; x++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(int y = 0; y < r; y++) {
            while(maxStack.top().first <= arr[y][x]) maxStack.pop();
            maxUp[y][x] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], y));
        }
    }

    for(int x = 0; x < c; x++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, r));
        for(int y = r-1; y >= 0; y--) {
            while(maxStack.top().first <= arr[y][x]) maxStack.pop();
            maxDown[y][x] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], y));
        }
    }

    // for(auto i : {maxUp, maxDown, maxLeft, maxRight}) {
    //     for(auto j : i) {
    //         for(auto k : j) cout << k << ' ';
    //         cout << '\n';
    //     }
    //     cout << '\n';
    // }

    for(int x = 1; x < c-1; x++) {
        for(int y = 1; y < r-1; y++) {
            bool pwede = true;
            pwede &= (0 <= maxUp[y][x] && maxUp[y][x] < r);
            pwede &= (0 <= maxDown[y][x] && maxDown[y][x] < r);
            pwede &= (0 <= maxLeft[x][y] && maxLeft[x][y] < c);
            pwede &= (0 <= maxRight[x][y] && maxRight[x][y] < c);

            if(pwede) {
                valid.emplace(make_tuple(maxLeft[x][y]+1, maxRight[x][y]-1, maxUp[y][x]+1, maxDown[y][x]-1));
            }
        }
    }


    for(int y = 0; y < r; y++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(int x = 0; x < c; x++) {
            while(maxStack.top().first < arr[y][x]) maxStack.pop();
            maxLeft[x][y] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], x));
        }
    }

    // process first right
    for(int y = 0; y < r; y++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, c));
        for(int x = c-1; x >= 0; x--) {
            while(maxStack.top().first < arr[y][x]) maxStack.pop();
            maxRight[x][y] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], x));
        }
    }

    for(int x = 0; x < c; x++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(int y = 0; y < r; y++) {
            while(maxStack.top().first < arr[y][x]) maxStack.pop();
            maxUp[y][x] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], y));
        }
    }

    for(int x = 0; x < c; x++) {
        stack<pair<int, int>> maxStack;
        maxStack.push(make_pair(7'000'005, r));
        for(int y = r-1; y >= 0; y--) {
            while(maxStack.top().first < arr[y][x]) maxStack.pop();
            maxDown[y][x] = maxStack.top().second;
            maxStack.push(make_pair(arr[y][x], y));
        }
    }


    // for(auto i : {maxUp, maxDown, maxLeft, maxRight}) {
    //     for(auto j : i) {
    //         for(auto k : j) cout << k << ' ';
    //         cout << '\n';
    //     }
    //     cout << '\n';
    // }

    vector<MinMaxST> segtreeY, segtreeX;

    for(int i = 0; i < r; i++) segtreeY.push_back(MinMaxST(0, c-1, maxDown[i], maxUp[i]));
    for(int i = 0; i < c; i++) segtreeX.push_back(MinMaxST(0, r-1, maxRight[i], maxLeft[i]));

    ll ans = 0;

    for(auto i : valid) {
        bool validRect = true;

        int xl = get<0>(i);
        int xr = get<1>(i);
        int yu = get<2>(i);
        int yd = get<3>(i);

        // cout << xl << ' ' << xr << ' ' << yu << ' ' << yd << '\n';
        // cout << maxDownST[yu-1].qry(xl, xr) << ' ' << maxUpST[yd+1].qry(xl, xr) << '\n';
        // cout << maxRightST[xl-1].qry(yu, yd) << ' ' << maxLeftST[xr+1].qry(yu, yd) << '\n';

        validRect &= segtreeY[yu-1].qryMin(xl, xr) > yd;
        validRect &= segtreeY[yd+1].qryMax(xl, xr) < yu;

        validRect &= segtreeX[xl-1].qryMin(yu, yd) > xr;
        validRect &= segtreeX[xr+1].qryMax(yu, yd) < xl;

        ans += validRect;
    }

    return ans;
}

• 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