Submission #551417

#	Time	Username	Problem	Language	Result	Execution time	Memory
551417		PiejanVDC	Rectangles (IOI19_rect)	C++17	13 / 100	238 ms	86276 KiB

rect

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

long long count_rectangles(vector<vector<int>> v) {
    long long ans = 0;
    const int n = (int)v.size();
    const int m = (int)v[0].size();
    vector<vector<int>>sum(n+1, vector<int>(m+1,0));
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= m ; j++) {
            sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + v[i-1][j-1];
        }
    }

    auto get = [&] (int x1, int y1, int x2, int y2) -> int {
        return sum[x1][y1] - sum[x2-1][y1] - sum[x1][y2-1] + sum[x2-1][y2-1];
    };

    for(int i = 1 ; i < n-1 ; i++) {
        for(int j = 1 ; j < m-1 ; j++) {
            if(v[i][j] == 0 && v[i][j+1] == 1) {
                int l = 1, r = i, f, s;
                while(l <= r) {
                    int mid = (l+r)/2;
                    if(get(i+1, j+1, mid+1, j+1) == 0)
                        f = mid, r = mid-1;
                    else
                        l = mid+1;
                }
                l = 1, r = j;
                while(l <= r) {
                    int mid = (l+r)/2;
                    if(get(i+1, j+1, i+1, mid+1) == 0)
                        s = mid, r = mid-1;
                    else
                        l = mid+1;
                }
                if(get(i+1, j+1, f+1, s+1) != 0)
                    continue;
                if(get(i+1, j+2, f+1, j+2) == i - f + 1 && get(i+2, j+1, i+2, s+1) == j - s + 1 && get(i+1, s, f+1, s) == i - f + 1 && get(f, j+1, f, s+1) == j - s + 1) {
                    ans++;
                }
            }
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:41:89: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |                 if(get(i+1, j+2, f+1, j+2) == i - f + 1 && get(i+2, j+1, i+2, s+1) == j - s + 1 && get(i+1, s, f+1, s) == i - f + 1 && get(f, j+1, f, s+1) == j - s + 1) {
      |                                                                                       ~~^~~
rect.cpp:41:49: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |                 if(get(i+1, j+2, f+1, j+2) == i - f + 1 && get(i+2, j+1, i+2, s+1) == j - s + 1 && get(i+1, s, f+1, s) == i - f + 1 && get(f, j+1, f, s+1) == j - s + 1) {
      |                                               ~~^~~

• 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