Submission #1048010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048010		mariaclara	Rectangles (IOI19_rect)	C++17	72 / 100	3583 ms	1048628 KiB

rect

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first 
#define sc second
 
ll count_rectangles(vector<vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	// primeiro eu calculo os pares uteis
	vector<int> line[n][m], col[n][m], val_l[n][m], val_c[n][m];

	// calculando os pares na linha
	for(int i = 0; i < n; i++) {
		vector<int> r(m);

		for(int j = 0; j < m; j++) {
			r[j] = j-1;
			// acho o primeiro cara maior ou igual (com indice menor)
			while(r[j] >= 0 and a[i][r[j]] < a[i][j]) r[j] = r[r[j]];
			if(r[j] >= 0 and r[j]+1 < j) line[i][j].pb(r[j]);
		}

		for(int j = m-1; j >= 0; j--) {
			r[j] = j+1;
			// acho o primeiro cara maior ou igual (com indice maior)
			while(r[j] < m and a[i][r[j]] < a[i][j]) r[j] = r[r[j]];
			if(r[j] < m and j+1 < r[j] and a[i][j] != a[i][r[j]]) line[i][r[j]].pb(j);
		}
	}

	// calculando os pares na coluna
	for(int j = 0; j < m; j++) {
		vector<int> r(n);

		for(int i = 0; i < n; i++) {
			r[i] = i-1;
			// acho o primeiro cara maior ou igual (com indice menor)
			while(r[i] >= 0 and a[r[i]][j] < a[i][j]) r[i] = r[r[i]];
			if(r[i] >= 0 and r[i]+1 < i) col[i][j].pb(r[i]);
		}

		for(int i = n-1; i >= 0; i--) {
			r[i] = i+1;
			// acho o primeiro cara maior ou igual (com indice maior)
			while(r[i] < n and a[r[i]][j] < a[i][j]) r[i] = r[r[i]];
			if(r[i] < n and i+1 < r[i] and a[i][j] != a[r[i]][j]) col[r[i]][j].pb(i);
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			sort(all(line[i][j]));
			sort(all(col[i][j]));

			val_l[i][j].resize(sz(line[i][j]), i);
			for(int k = 0, ptr = 0; i != 0 and k < sz(line[i][j]); k++) {
				while(ptr < sz(line[i-1][j]) and line[i-1][j][ptr] < line[i][j][k]) ptr++;
				if(ptr >= sz(line[i-1][j])) break;
				if(line[i-1][j][ptr] == line[i][j][k]) val_l[i][j][k] = val_l[i-1][j][ptr];
			}

			val_c[i][j].resize(sz(col[i][j]), j);
			for(int k = 0, ptr = 0; j != 0 and k < sz(col[i][j]); k++) {
				while(ptr < sz(col[i][j-1]) and col[i][j-1][ptr] < col[i][j][k]) ptr++;
				if(ptr >= sz(col[i][j-1])) break;
				if(col[i][j-1][ptr] == col[i][j][k]) val_c[i][j][k] = val_c[i][j-1][ptr];
			}
		}
	}

	// for(int i = 0; i < n; i++) {
	// 	for(int j = 0; j < m; j++) {
	// 		for(int x = 0; x < sz(line[i][j]); x++)
	// 			cout << "line " << i << ": " << line[i][j][x] << " " << j << " " << val_l[i][j][x] << "\n";
	// 	}
	// }

	// for(int j = 0; j < m; j++) {
	// 	for(int i = 0; i < n; i++) {
	// 		for(int x = 0; x < sz(col[i][j]); x++)
	// 			cout << "col " << j << ": " << col[i][j][x] << " " << i << " " << val_c[i][j][x] << "\n";
	// 	}
	// }

	// Toda parte anterior é em O(n*m*log)
	// Parte que calcula a resposta em O(n*m*min(n,m))

	int ans = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < m; j++) {
			// aqui nos calculamos os retangulos com borda (i,j), ou seja:
			// (i,j-1), (i,j-2), ..., (i,j-x) fazem parte do retangulo
			// (i-1,j), (i-2,j), ..., (i-y,j) fazem parte do retangulo
			for(int x = 0; x < sz(col[i][j-1]); x++) {
				for(int y = 0; y < sz(line[i-1][j]); y++) {
					int v1 = col[i][j-1][x], v2 = val_c[i][j-1][x]; 
					int v3 = line[i-1][j][y], v4 = val_l[i-1][j][y];
					if(v4 <= v1+1 and v2 <= v3+1) ans++; 
				}
			}
		}
	}

	return ans;
}

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