Submission #1219317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219317		12baater	Rectangles (IOI19_rect)	C++20	25 / 100	5095 ms	67908 KiB

rect

#include "rect.h"
#include <iostream>
#include <set>
#include <vector>
using namespace std;

vector<int> LOG2;
const int INF = 1E8;

struct ST {
	int n;
	vector<int> seg;
	ST (int N) : n(N), seg(2*N, 0) {}
	
	void push(int pos, int num) {
		pos += n;
		seg[pos] = num;
	}

	void init() {
		for (int i = n-1; i > 0; i--) {
			seg[i] = max(seg[2*i], seg[2*i+1]);
		}
	}

	int query(int l, int r) {
		l += n; r += n + 1;
		int ret = 0;
		while (l < r) {
			if(l&1) ret = max(ret, seg[l++]);
			if(r&1) ret = max(ret, seg[--r]);
			r >>= 1;
			l >>= 1;
		}
		return ret;
	}

	void print() {
		for (int i = 1; i <= LOG2[seg.size()]+1; i++) {
			for (int j = (1<<(i-1)); j < (1<<i); j++) {
				cout << seg[j] << " ";
			}
			cout << endl;
		}
	}
};

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	long long ans = 0;
	LOG2.push_back(0);
	LOG2.push_back(0);
	for(int i = 2; i <= 5*max(n,m); i++) LOG2.push_back(LOG2[i/2]+1);
	vector<ST> rowTrees(n, ST(m));
	vector<ST> columnTrees(m, ST(n));

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			rowTrees[i].push(j, a[i][j]);
			columnTrees[j].push(i,a[i][j]);
		}
	}
	for(int i = 0; i < n; i++) {
		rowTrees[i].init();
	}
	for(int i = 0; i < m; i++) {
		columnTrees[i].init();
	}

	for(int r_1 = 1; r_1 < n-1; r_1++) {
		for (int c_1 = 1; c_1 < m-1; c_1++) {
			for (int r_2 = r_1; r_2 < n-1; r_2++) {
				for (int c_2 = c_1; c_2 < m-1; c_2++) {
					bool valid = true;
					// cout << "--------------------------\n";
					for (int column = c_1; column <= c_2; column++) {
						int num = columnTrees[column].query(r_1,r_2); 
						if (num >= a[r_1-1][column] || num >= a[r_2+1][column]) valid = false;
					}
					for (int row = r_1; row <= r_2; row++) {
						int num = rowTrees[row].query(c_1,c_2);
						// printf("row: %d, c_1: %d, c_2: %d, max: %d\n",row,c_1,c_2,num);
						// rowTrees[row].print();
						if (num >= a[row][c_1-1] || num >= a[row][c_2+1]) valid = false;
					}
					ans += valid;
					// if(valid) printf("(%d, %d) && (%d, %d)\n", r_1, c_1, r_2, c_2);
				}
			}
		}
	}
	return ans;
}

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