Submission #244893

#	Time	Username	Problem	Language	Result	Execution time	Memory
244893		crossing0ver	Rectangles (IOI19_rect)	C++17	37 / 100	5095 ms	76792 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;
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];
			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 count_rectangles(vector<vector<int> > a) {
	 n = a.size();
	 m = a[0].size();
	 precalculate(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;
	/* 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';
	 }*/
	 
}
#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
*/
	
}
#endif

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