제출 #1290760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290760		julia_08	Rectangles (IOI19_rect)	C++20	0 / 100	1 ms	348 KiB

rect

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

using ll = long long;

using namespace std;

const int MAXN = 210;

int mat[MAXN][MAXN];

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

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

int n, m;

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] = q.top();
			else col[i][j] = 1;

			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)

	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]);

				for(int l=(j - 1); l>min_col; l--){
					if(row[i][l][0] <= k && row[k][l][1] >= i){
						// cout << "(" << k + 1 << ", " << l << "), (" << i - 1 << ", " << j - 1 << ")" << endl;
						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