Submission #1216408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216408		jasonic	Rectangles (IOI19_rect)	C++20	59 / 100	1365 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 MaxST{
    short l, r;
    MaxST *lt, *rt;
    short mx;

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

    MaxST(short bl, short br, vector<short> &a) {
        lt = rt = nullptr;
        l = bl, r = br;

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

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

struct MinST{
    short l, r;
    MinST *lt, *rt;
    short mx;

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

    MinST(short bl, short br, vector<short> &a) {
        lt = rt = nullptr;
        l = bl, r = br;

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

    short qry(int ql, int qr) {
        if(qr < l || r < ql) return 8'000;
        if(ql <= l && r <= qr) return mx;
        else return min(lt->qry(ql, qr), rt->qry(ql, qr));
    }
};

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

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

    set<tuple<short, short, short, short>> valid;

    // process first left
    for(short y = 0; y < r; y++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(short 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(short y = 0; y < r; y++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, c));
        for(short 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(short x = 0; x < c; x++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(short 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(short x = 0; x < c; x++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, r));
        for(short 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(short x = 1; x < c-1; x++) {
        for(short 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));
            }
        }
    }


    // process first left
    for(short y = 0; y < r; y++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(short 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(short y = 0; y < r; y++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, c));
        for(short 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(short x = 0; x < c; x++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, -1));
        for(short 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(short x = 0; x < c; x++) {
        stack<pair<int, short>> maxStack;
        maxStack.push(make_pair(7'000'005, r));
        for(short 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<MinST> maxDownST, maxRightST;
    vector<MaxST> maxLeftST, maxUpST;
    for(int i = 0; i < r; i++) {
        maxUpST.push_back(MaxST(0, c-1, maxUp[i]));
        maxDownST.push_back(MinST(0, c-1, maxDown[i]));
    }

    for(int i = 0; i < c; i++) {
        maxLeftST.push_back(MaxST(0, r-1, maxLeft[i]));
        maxRightST.push_back(MinST(0, r-1, maxRight[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 &= maxDownST[yu-1].qry(xl, xr) > yd;
        validRect &= maxUpST[yd+1].qry(xl, xr) < yu;

        validRect &= maxRightST[xl-1].qry(yu, yd) > xr;
        validRect &= maxLeftST[xr+1].qry(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