Submission #1215177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215177		jasonic	Rectangles (IOI19_rect)	C++20	0 / 100	3681 ms	79192 KiB

rect

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

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

int r, c;

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

ll count_rectangles(vector<vector<int>> arr) {
    r = size(arr);
    c = size(arr[0]);

    vector<vector<int>> maxUp(r, vector<int>(c, -1));
    vector<vector<int>> maxDown(r, vector<int>(c, -1));
    vector<vector<int>> maxLeft(r, vector<int>(c, -1));
    vector<vector<int>> maxRight(r, vector<int>(c, -1));

    for(int y = 0; y < r; y++) {
        for(int x = 0; x < c; x++) {
            int xl = x-1, xr = x+1;
            int yu = y-1, yd = y+1;

            for(; xl >= 0; xl--) if(arr[y][xl] > arr[y][x]) break;
            for(; xr < c; xr++) if(arr[y][xr] > arr[y][x]) break;
            for(; yu >= 0; yu--) if(arr[yu][x] > arr[y][x]) break;
            for(; yd < r; yd++) if(arr[yd][x] > arr[y][x]) break;

            maxUp[y][x] = yu;
            maxDown[y][x] = yd;
            maxLeft[y][x] = xl;
            maxRight[y][x] = xr;
        }
    }

    vector<vector<int>> vis(r, vector<int>(c, 0));
    int thing = 1;
    ll ans = 0;

    for(int y = 1; y < r-1; y++) {
        for(int x = 1; x < c-1; x++) {
            int mnX = maxLeft[y][x], mxX = maxRight[y][x], mxY = maxDown[y][x], mnY = maxUp[y][x];
            int mnX2, mxX2, mnY2, mxY2;
            mnX2 = mxX2 = x;
            mnY2 = mxY2 = y;
            vis[y][x] = thing;
            int sz = 1;

            queue<pair<int, int>> bfs;
            bfs.push(make_pair(y, x));

            while(!bfs.empty()) {
                pair<int, int> curr = bfs.front(); bfs.pop();

                for(int i = 0; i < 4; i++) {
                    int ny = curr.first + dy[i];
                    int nx = curr.second + dx[i];

                    if(0 <= ny && ny < r && 0 <= nx && nx < c) if(vis[ny][nx] != thing) if(arr[curr.first][curr.second] >= arr[ny][nx]) {
                        bfs.push(make_pair(y, x));
                        mnX = min(maxLeft[ny][nx], mnX);
                        mxX = max(maxRight[ny][nx], mxX);
                        mnY = min(maxUp[ny][nx], mnY);
                        mxY = max(maxDown[ny][nx], mxY);

                        mnX2 = min(mnX2, nx);
                        mxX2 = max(mxX2, nx);
                        mnY2 = min(mnY2, ny);
                        mxY2 = max(mxY2, ny);

                        vis[ny][nx] = thing;
                        sz++;
                    }
                }
            }

            // cout << x << ' ' << y << '\n';
            // cout << sz << '\n';
            // cout << mnX2 << ' ' << mxX2 << '\n';
            // cout << mnY2 << ' ' << mxY2 << '\n';
            // cout << mnX << ' ' << mxX << '\n';
            // cout << mnY << ' ' << mxY << '\n';

            if(sz == (mxX2 - mnX2 + 1) * (mxY2 - mnY2 + 1)) if(mnX + 1 == mnX2) if(mxX - 1 == mxX2) if(mnY + 1 == mnY2) if(mxY - 1 == mxY2) if(0 != mnY2 && mnY2 != r-1 && 0 != mnX2 && mnX2 != c-1) {
                // cout << "added\n";
                ans++;
            }
            
            // cout << '\n';
            thing++;
        }
    }

    return ans;
}

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