Submission #1088925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088925		VMaksimoski008	Rectangles (IOI19_rect)	C++17	23 / 100	1408 ms	453968 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

ll count_rectangles(vector<vector<int> > mat) {
    int n = mat.size(), m = mat[0].size();
    if(n < 3 || m < 3) return 0;

    ll ans = 0;

    vector<int> R[n][m], D[n][m];
    stack<pii> st;

    for(int i=0; i<n; i++) {
        while(!st.empty()) st.pop();
        for(int j=m-1; j>=0; j--) {
            while(!st.empty() && st.top().first < mat[i][j]) st.pop();
            if(!st.empty() && st.top().second - j >= 2) R[i][j].push_back(st.top().second);
            st.push({ mat[i][j], j });
        }

        while(!st.empty()) st.pop();
        for(int j=0; j<m; j++) {
            while(!st.empty() && st.top().first < mat[i][j]) st.pop();
            if(!st.empty() && j - st.top().second >= 2) R[i][st.top().second].push_back(j);
            st.push({ mat[i][j], j });
        }
    }

    for(int j=0; j<m; j++) {
        while(!st.empty()) st.pop();
        for(int i=n-1; i>=0; i--) {
            while(!st.empty() && st.top().first < mat[i][j]) st.pop();
            if(!st.empty() && st.top().second - i >= 2) D[i][j].push_back(st.top().second);
            st.push({ mat[i][j], i });
        }

        while(!st.empty()) st.pop();
        for(int i=0; i<n; i++) {
            while(!st.empty() && st.top().first < mat[i][j]) st.pop();
            if(!st.empty() && i - st.top().second >= 2) D[st.top().second][j].push_back(i);
            st.push({ mat[i][j], i });
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(R[i][j].size() == 2 && R[i][j][0] == R[i][j][1]) R[i][j].pop_back();
            if(D[i][j].size() == 2 && D[i][j][0] == D[i][j][1]) D[i][j].pop_back();
        }
    }

    for(int i=1; i+1<n; i++) {
        for(int j=0; j<m; j++) {
            for(int &l : R[i][j]) {
                map<int, int> cnt;
                for(int x=j+1; x<l; x++)
                    for(int &y : D[i-1][x]) cnt[y]++;
                vector<int> opt;
                for(auto &[o, c] : cnt) if(c == l - j - 1) opt.push_back(o-1);
                for(int &k : opt) {
                    bool ok = 1;
                    for(int x=i; x<=k&&ok; x++) {
                        bool ok2 = 0;
                        for(int &y : R[x][j]) if(y == l) ok2 = 1;
                        if(!ok2) ok = 0;
                    }
                    ans += ok;
                }
            }
        }
    }

    return ans;
}

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