Submission #1290784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290784		julia_08	Rectangles (IOI19_rect)	C++20	0 / 100	5094 ms	83508 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using ll = long long;

using namespace std;

const int MAXN = 2510;

int mat[MAXN][MAXN];

int row[MAXN][MAXN][2], col[MAXN][MAXN][2];

// row[i][j] = primeiro linha (para cima) que tem val >=
// col[i][j] = primeira coluna (para esquerda) que tem val >=

int n, m;

ll solve_3(){

	ll ans = 0;

	for(int i=1; i<=m; i++){

		int cur_max = 0;

		for(int j=(i + 1); j<m; j++){

			if(mat[2][i] >= mat[1][i] || mat[2][i] >= mat[3][i]) break;

			cur_max = max(cur_max, mat[2][j]);

			if(mat[2][i] > cur_max && mat[2][j + 1] > cur_max) ans ++;

		}
	}

	return ans;

}

ll count_rectangles(vector<vector<int>> a){

	n = (int) a.size();

	m = (int) a[0].size();

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			mat[i + 1][j + 1] = a[i][j];
		}
	}

	for(int i=1; i<=n; i++){

		stack<int> q;

		for(int j=1; j<=m; j++){

			while(!q.empty() && mat[i][q.top()] < mat[i][j]) q.pop();

			if(!q.empty()) col[i][j][0] = q.top();
			else col[i][j][0] = 1;

			q.push(j);

		}

	}

	for(int i=1; i<=n; i++){

		stack<int> q;

		for(int j=m; j>=1; j--){

			while(!q.empty() && mat[i][q.top()] < mat[i][j]) q.pop();

			if(!q.empty()) col[i][j][1] = q.top();
			else col[i][j][1] = m;

			q.push(j);

		}

	}

	for(int j=1; j<=m; j++){

		stack<int> q;

		for(int i=1; i<=n; i++){

			while(!q.empty() && mat[q.top()][j] < mat[i][j]) q.pop();

			if(!q.empty()) row[i][j][0] = q.top();
			else row[i][j][0] = 1;

			q.push(i);

		}

	}

	for(int j=1; j<=m; j++){

		stack<int> q;

		for(int i=n; i>=1; i--){

			while(!q.empty() && mat[q.top()][j] < mat[i][j]) q.pop();

			if(!q.empty()) row[i][j][1] = q.top();
			else row[i][j][1] = n;

			q.push(i);

		}

	}

	/*
	cout << "***row***" << endl;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cout << i << " " << j << " " << row[i][j] << endl;
		}
	}

	cout << "***col***" << endl;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cout << i << " " << j << " " << col[i][j] << endl;
		}
	}
	*/

	// cout << "calculei row / col" << endl;

	// n * (m * m)

	if(n == 3) return solve_3();

	ll ans = 0;

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){

			int min_col = 1;

			for(int k=(i - 2); k>=1; k--){

				min_col = max(min_col, col[k + 1][j][0]);

				for(int l=(j - 1); l>min_col; l--){
					if(row[i][l][0] <= k && row[k][l][1] >= i){

						bool ok = true;

						for(int x=(k + 1); x<i; x++){
							if(col[x][l - 1][1] < j){
								ok = false;
							}
						}

						// cout << "(" << k + 1 << ", " << l << "), (" << i - 1 << ", " << j - 1 << ")" << endl;
						if(ok) ans ++;


					} else break;
				}

			}

		}
	}

	return ans;

}

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