Submission #827122

#	Time	Username	Problem	Language	Result	Execution time	Memory
827122		vjudge1	Rectangles (IOI19_rect)	C++17	13 / 100	395 ms	112504 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ll long long
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
const int N = 2600;
int a[N][N],n,m,pr[N][N];
int calc(int lx,int rx,int ly,int ry) {
	if(lx > rx || ly > ry)return 0;
	return pr[rx][ry] - pr[rx][ly - 1] - pr[lx - 1][ry] + pr[lx - 1][ly - 1];
}
bool check(int lx,int rx,int ly,int ry) {
	if(calc(lx + 1,rx - 1,ly + 1,ry - 1) || rx - lx + 1 < 3 || ry - ly + 1 < 3)return 0;
	if(calc(lx + 1,rx - 1,ly,ly) != rx - lx - 1 || calc(lx + 1,rx - 1,ry,ry) != rx - lx - 1)return 0;
	if(calc(lx,lx,ly + 1,ry - 1) != ry - ly - 1 || calc(rx,rx,ly + 1,ry - 1) != ry - ly - 1)return 0;
	return 1; 
}
int firh(int x,int y) {
	int l = x + 1,r = n,ans = n + 5;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(calc(x + 1,mid,y,y)) {
			ans = mid;
			r = mid - 1;
		}else {
			l = mid + 1;
		}
	}
	return ans;
}
int firg(int x,int y) {
	int l = y + 1,r = m,ans = m + 5;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(calc(x,x,y + 1,mid)) {
			ans = mid;
			r = mid - 1;
		}else {
			l = mid + 1;
		}
	}
	return ans;
}
ll count_rectangles(vector<vector<int> > A) {
	n = A.size();
	m = A[0].size();
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < m;j++) {
			a[i + 1][j + 1] = A[i][j];
		}
	}
	for(int i = 1;i <= n;i++) {
		int tek = 0;
		for(int j = 1;j <= m;j++) {
			tek += a[i][j];
			pr[i][j] = pr[i - 1][j] + tek;
		}
	}
	ll ans = 0;
	for(int i = 1;i < n - 1;i++) {
		for(int j = 1;j < m - 1;j++) {
			int fx = firh(i,j + 1),fy = firg(i + 1,j);
			ans += check(i,fx,j,fy);
			//if(check(i,fx,j,fy))cout << i << " " << j << " " << fx << " " << fy << en;
		}
	}
	return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/

• 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