Submission #1151796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151796		Pacybwoah	Rectangles (IOI19_rect)	C++20	13 / 100	285 ms	123216 KiB

rect

#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<utility>
using namespace std;
typedef long long ll;

long long count_rectangles(std::vector<std::vector<int> > a) {
	ll ans = 0;
	int n = (int)a.size();
	int m = (int)a[0].size();
	if(n <= 2 || m <= 2) return 0;
	vector<vector<int>> pre(n, vector<int>(m));
    pre[0][0] = a[0][0];
    for(int i = 1; i < n; i++) pre[i][0] = pre[i - 1][0] + a[i][0];
    for(int i = 1; i < m; i++) pre[0][i] = pre[0][i - 1] + a[0][i];
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
    }
    auto calc = [&](int a, int b, int c, int d){
        int res = pre[b][d];
        if(c > 0) res -= pre[b][c - 1];
        if(a > 0) res -= pre[a - 1][d];
        if(c > 0 && a > 0) res += pre[a - 1][c - 1];
        return res;
    };
    vector<vector<int>> lstr(n, vector<int>(m)), lstc(n, vector<int>(m));
    for(int i = 1; i < n - 1; i++){
        lstr[i][0] = 1;
        for(int j = 1; j < m - 1; j++){
            if(a[i][j] == 0 && a[i + 1][j] == 1){
                if(lstr[i][j - 1] == -1) lstr[i][j] = j;
                else lstr[i][j] = lstr[i][j - 1];
            }
            else lstr[i][j] = -1;
        }
    }
    for(int i = 1; i < m - 1; i++){
        lstc[0][i] = 1;
        for(int j = 1; j < n - 1; j++){
            if(a[j][i] == 0 && a[j][i + 1] == 1){
                if(lstc[j - 1][i] == -1) lstc[j][i] = j;
                else lstc[j][i] = lstc[j - 1][i];
            }
            else lstc[j][i] = -1;
        }
    }
    for(int i = 1; i < n - 1; i++){
        for(int j = 1; j < m - 1; j++){
            if(lstr[i][j] >= 0 && lstc[i][j] >= 0){
                int a = lstc[i][j], b = i, c = lstr[i][j], d = j;
                if(calc(a, b, c, d) == 0 && calc(a, b, c - 1, c - 1) == b - a + 1 && calc(a, b, d + 1, d + 1) == b - a + 1 && calc(a - 1, a - 1, c, d) == d - c + 1 && calc(b + 1, b + 1, c, d) == d - c + 1) ans++;
            }
        }
    }
	return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run rect2.cpp grader.cpp

• 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