Submission #397723

#	Time	Username	Problem	Language	Result	Execution time	Memory
397723		ly20	Rectangles (IOI19_rect)	C++17	13 / 100	308 ms	184568 KiB

rect

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


const int MAXN = 2512;
int n, m;
long long sp[MAXN][MAXN];
int dir[MAXN][MAXN], bax[MAXN][MAXN];
long long area(int i, int j, int k, int l) {
    return sp[k][l] - sp[k][j - 1] - sp[i - 1][l] + sp[i - 1][j - 1];
}
int tb[MAXN][MAXN];
long long count_rectangles(vector<vector<int> > ts) {
	n = ts.size();
	m = ts[0].size();
	if(n < 3 || m < 3) return 0;
    long long resp = 0;
	for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            tb[i + 1][j + 1] = ts[i][j];
        }
	}
	for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            sp[i][j] = tb[i][j] + sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];
        }
	}
	for(int i = n; i >= 1; i--) {
        for(int j = m; j >= 1; j--) {
            if(tb[i][j] == 0) {
                if(i == n) bax[i][j] = n + 1;
                else bax[i][j] = bax[i + 1][j];
                if(j == m) dir[i][j] = m + 1;
                else dir[i][j] = dir[i][j + 1];
            }
            else {
                bax[i][j] = i;
                dir[i][j] = j;
            }
        }
	}
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int lar = dir[i][j] - j, alt = bax[i][j] - i;
            if(lar == 0 || dir == 0) continue;
            int ptx = i + alt - 1, pty = j + lar - 1;
            //printf("%d %d %d %d\n", i, j, ptx, pty);
            //printf("%lld %d %d %d %d\n", area(i, j, ptx, pty), sp[ptx][pty], sp[ptx][j - 1], sp[i - 1][pty], sp[i - 1][j - 1]);
            if(area(i, j, ptx, pty) != 0) continue;
            if(area(i - 1, j, i - 1, pty) != lar) continue;
            if(area(ptx + 1, j, ptx + 1, pty) != lar) continue;
            if(area(i, j - 1, ptx, j - 1) != alt) continue;
            if(area(i, pty + 1, ptx, pty + 1) != alt) continue;
            resp++;
        }
    }
	return resp;
}

• 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