Submission #244956

#	Time	Username	Problem	Language	Result	Execution time	Memory
244956		crossing0ver	Rectangles (IOI19_rect)	C++17	50 / 100	5059 ms	196728 KiB

rect

#include<bits/stdc++.h>
#define ll long long 
#ifndef local
#include "rect.h"
#endif
using namespace std;
int L[2505][2505][2],R[2505][2505][2],n,m;
ll sum[2505][2505];
void clearStack(stack<int>& s) {
	while(!s.empty()) s.pop();
}
void precalculate(vector<vector<int> > &a) {
	for (int i = 0; i < n; i++) {
		stack<int> s;
		for (int j = 0; j < m; j++) {
			int val = a[i][j];
			sum[i][j] = (j ? sum[i][j-1] : 0) + (i ? sum[i-1][j] : 0) - ( i && j ? sum[i-1][j-1]: 0) + a[i][j];
			while(!s.empty() && a[i][s.top()] < val)
				s.pop();
			L[i][j][0] = (s.empty() ? 0 : s.top() + 1);
			s.push(j);
		}
		clearStack(s);
		for (int j = m-1; j > -1; j--) {
			int val = a[i][j];
			while(!s.empty() && a[i][s.top()] < val)
				s.pop();
			R[i][j][0] = (s.empty() ? m-1 : s.top() - 1);
			s.push(j);
		}																		
	}
	for (int i = 0; i < m; i++) {
		stack<int> s;
		for (int j = 0; j < n; j++) {
			int val = a[j][i];
			while(!s.empty() && a[s.top()][i] < val)
				s.pop();
			L[j][i][1] = (s.empty() ? 0 : s.top() + 1);
			s.push(j);
		}
		clearStack(s);
		for (int j = n-1; j > -1; j--) {
			int val = a[j][i];
			while(!s.empty() && a[s.top()][i] < val)
				s.pop();
			R[j][i][1] = (s.empty() ? n-1 : s.top() - 1);
			s.push(j);
		}																		
	}
}
ll CaseSmall(vector<vector<int> > &a) {
	ll cnt = 0;
	for (int xi = 1; xi < m-1; xi++)
	 for (int xj = xi; xj < m-1; xj++) 
	 for (int yi = 1; yi < n-1; yi++)
	 for (int yj = yi; yj < n-1; yj++) {
	 	bool flag = 1;
	 	for (int k = xi; k <= xj && flag;k++) {
	 		if (R[yi-1][k][1] < yj) flag = 0;
	 		if (L[yj+1][k][1] > yi) flag = 0;
		}
		for (int k = yi; k <= yj && flag;k++) {
	 		if (R[k][xi-1][0] < xj) flag = 0;
	 		if (L[k][xj+1][0] > xi) flag = 0;
		 }
		 if (flag) cnt++;
	 }
	 return cnt;
}
ll SumRect(int xi,int xj,int yi,int yj) {
	return sum[yj][xj] + (yi && xi ? sum[yi-1][xi-1] : 0) -
	 (yi ? sum[yi-1][xj] : 0) -  (xi ? sum[yj][xi-1] : 0);	
}
ll CaseZero(vector<vector<int> > &a) {
	ll cnt = 0;
	for (int i = 0; i < n-1; i++)
	for (int j = 0; j < m-1; j++) {
		if (a[i][j+1]!= 1 || a[i+1][j] != 1) continue;
		int r = R[i+1][j][0];
		int d = R[i][j+1][1];
		r++;
		d++;
		if (r <= j+1 || d <= i+1 || r == m || d == n) continue;
		int x = SumRect(j,r,i,d);
		cnt += (SumRect(j+1,r - 1,i+1,d-1) == 0
		&& x == (2*(r - i + d - j)
		- (1 - a[i][j]) -(1 - a[i][r]) - (1-a[d][j]) - (1 - a[d][r])));
	}
	return cnt;
	
}
ll count_rectangles(vector<vector<int> > a) {
	 n = a.size();
	 m = a[0].size();
	 precalculate(a);
	 bool flag = 1;
	 for (int i = 0; i < n;i++)
	 for (int j = 0; j < m;j++)
	 	if (a[i][j] > 1) flag = 0;
	if (flag) return CaseZero(a);
	 ll cnt = 0; 
	 if (n <= 700 || m <= 700) return CaseSmall(a);
	/* for (int i = 0; i < n; i++)
	 for (int j = 0;j < m; j++) {
			cout << i <<' '<<j << ":\t" << "left " << L[i][j][0] <<" right "<< R[i][j][0] <<" up " << L[i][j][1] <<" down " << R[i][j][1] <<'\n';
	 }*/
	 return 0;
	 
}
#ifdef local
main() {
	cin >> n >> m;
	vector<vector<int> > a(n,vector<int>(m));
	for (int i = 0;i < n; i++ )
	for (int j = 0; j < m; j++)
		cin >> a[i][j];
	cout << count_rectangles(a);
	/*
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
*/
/*
 4 4 
 1 1 1 1
 1 0 0 1
 1 1 1 1
 1 1 1 1*/
}
#endif

Compilation message (stderr)

rect.cpp: In function 'long long int CaseSmall(std::vector<std::vector<int> >&)':
rect.cpp:53:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int xi = 1; xi < m-1; xi++)
  ^~~
rect.cpp:68:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   return cnt;
   ^~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:101:6: warning: unused variable 'cnt' [-Wunused-variable]
   ll cnt = 0; 
      ^~~

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