Submission #396524

#	Time	Username	Problem	Language	Result	Execution time	Memory
396524		blue	Rectangles (IOI19_rect)	C++17	13 / 100	668 ms	336544 KiB

rect

#include "rect.h"
#include <vector>
using namespace std;


/*
For each (i, j)
T[i][j] = furthest row I such that T[I][j], T[I+1][j], ... T[i-1][j] all have height less than (i, j)
Similarly, D[i][j], R[i][j], L[i][j]

A rectangle (r1, r2, c1, c2) is good if(minD[r1-1][c1..c2] > r2) and so on
*/

vector< vector<int> > A;

int cc = 0;
vector<int> t, l, d, r;
vector<int> s;

int n, m;


void dfs(int i, int j)
{
    if(A[i][j]) return;
    A[i][j] = 1;

    t[cc-1] = min(t[cc-1], i);
    d[cc-1] = max(d[cc-1], i);
    l[cc-1] = min(l[cc-1], j);
    r[cc-1] = max(r[cc-1], j);
    s[cc-1]++;

    if(i > 0) dfs(i-1, j);
    if(i < n-1) dfs(i+1, j);
    if(j > 0) dfs(i, j-1);
    if(j < m-1) dfs(i, j+1);
}

long long count_rectangles(vector< vector<int> > a)
{
    A = a;

    n = A.size();
    m = A[0].size();

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(A[i][j]) continue;

            cc++;
            s.push_back(0);
            t.push_back(1e9);
            l.push_back(1e9);
            d.push_back(-1);
            r.push_back(-1);
            dfs(i, j);
        }

    long long res = 0;
    for(int i = 0; i < cc; i++)
    {
        if(t[i] == 0 || l[i] == 0 || d[i] == n-1 || r[i] == m-1) continue;
        if(s[i] == (d[i]-t[i]+1) * (r[i]-l[i]+1))
            res++;
    }

    return res;
}

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