Submission #826583

#	Time	Username	Problem	Language	Result	Execution time	Memory
826583		Josia	Rectangles (IOI19_rect)	C++17	100 / 100	3625 ms	1016764 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<vector<int>> A;
int N, M;
 
struct seg {
	vector<vector<int16_t>> sparse;
	bool minmax;
	int neut;
 
	int op(int a, int b) {
		if (minmax) return max(a,b);
		return min(a,b);
	}
 
 
	int query(int ql, int qr) {
		int len = qr-ql;
		int x = 1;
		int cnt = 0;
		while (x*2 <= len) {x*=2; cnt++;}

		assert(cnt < 13);

		if (cnt == 11) {x/=2; return op(op(sparse[10][ql],sparse[10][ql+x]), op(sparse[10][ql+x+x],sparse[10][qr-x+1]));}
		if (cnt == 12) {x/=4; return op(op(op(sparse[10][ql],sparse[10][ql+x]), op(sparse[10][ql+x+x],sparse[10][ql+x+x+x])), op(op(sparse[10][ql+x+x+x+x],sparse[10][ql+x+x+x+x+x]), op(sparse[10][ql+x+x+x+x+x],sparse[10][qr-x+1])));}

		return op(sparse[cnt][ql],sparse[cnt][qr-x+1]);
	}
 
	void init(int n, vector<int> a, bool type) {
		minmax = type;
		if (type) neut = -2e4;
		else neut = 2e4;

		sparse.assign(11, vector<int16_t>(n, neut));
 
		for (int i = 0; i<n; i++) sparse[0][i] = a[i];

		for (int i = 1; i<11; i++) {
			for (int j = 0; j<n-(1<<(i-1)); j++) {
				sparse[i][j] = op(sparse[i-1][j], sparse[i-1][j+(1<<(i-1))]);
			}
		}
	}
};
 
 
vector<vector<array<int16_t, 4>>> howFar;	// 1,0; 0,1; -1,0; 0,-1;
 
void makeHowFar() {
	howFar.assign(N, vector<array<int16_t, 4>>(M));
	for (int i = 0; i<N; i++) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> s;
		for (int j = 0; j<M; j++) {
			while (s.size() && s.top().first <= A[i][j]) {
				howFar[i][s.top().second][1] = j;
				s.pop();
			}
			s.push(pair<int, int>{A[i][j], j});
		}
		while (s.size()) {
			auto aa = s.top();
			s.pop();
			howFar[i][aa.second][1] = M-1;
		}
	}
 
	for (int i = 0; i<M; i++) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> s;
		for (int j = 0; j<N; j++) {
			while (s.size() && s.top().first <= A[j][i]) {
				howFar[s.top().second][i][0] = j;
				s.pop();
			}
			s.push(pair<int, int>{A[j][i], j});
		}
		while (s.size()) {
			auto aa = s.top();
			s.pop();
			howFar[aa.second][i][0] = N-1;
		}
	}
 
	for (int i = 0; i<N; i++) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> s;
		for (int j = M-1; j>=0; j--) {
			while (s.size() && s.top().first <= A[i][j]) {
				howFar[i][s.top().second][3] = j;
				s.pop();
			}
			s.push(pair<int, int>{A[i][j], j});
		}
		while (s.size()) {
			auto aa = s.top();
			s.pop();
			howFar[i][aa.second][3] = 0;
		}
	}
 
	for (int i = 0; i<M; i++) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> s;
		for (int j = N-1; j>=0; j--) {
			while (s.size() && s.top().first <= A[j][i]) {
				howFar[s.top().second][i][2] = j;
				s.pop();
			}
			s.push(pair<int, int>{A[j][i], j});
		}
		while (s.size()) {
			auto aa = s.top();
			s.pop();
			howFar[aa.second][i][2] = 0;
		}
	}
}
 
 
vector<seg> howFar10, howFar01, howFar_10, howFar0_1;
 
void makeHowFarSegs() {
	howFar10.resize(N);
	for (int i = 0; i<N; i++) {
		vector<int> a(M);
		for (int j = 0; j<M; j++) a[j] = howFar[i][j][0];
		howFar10[i].init(M, a, 0);
	}
 
	howFar01.resize(M);
	for (int i = 0; i<M; i++) {
		vector<int> a(N);
		for (int j = 0; j<N; j++) a[j] = howFar[j][i][1];
		howFar01[i].init(N, a, 0);
	}
 
	howFar_10.resize(N);
	for (int i = 0; i<N; i++) {
		vector<int> a(M);
		for (int j = 0; j<M; j++) a[j] = howFar[i][j][2];
		howFar_10[i].init(M, a, 1);
	}
 
	howFar0_1.resize(M);
	for (int i = 0; i<M; i++) {
		vector<int> a(N);
		for (int j = 0; j<N; j++) a[j] = howFar[j][i][3];
		howFar0_1[i].init(N, a, 1);
	}
}
 

unordered_map<int64_t, bool> vis;

bool verify(int top, int bottom, int left, int right) {		// top, bottom, left, right
 
	if (bottom-top < 2) return 0;
	if (right-left < 2) return 0;
 
	if(!(howFar10[top].query(left+1, right-1) >= bottom)) return 0;
	if(!(howFar_10[bottom].query(left+1, right-1) <= top)) return 0;
 
	if(!(howFar01[left].query(top+1, bottom-1) >= right)) return 0;
	if(!(howFar0_1[right].query(top+1, bottom-1) <= left)) return 0;
 
	if (vis[(int64_t) top + (int64_t) bottom*2500 + (int64_t) left*2500*2500 + (int64_t) right*2500*2500*2500]) return 0;
	vis[(int64_t) top + (int64_t) bottom*2500 + (int64_t) left*2500*2500 + (int64_t) right*2500*2500*2500] = 1;

	return 1;
}
 
 
 
int makeCandidates() {
	// candidates.resize((N-1)*(M-1)*8);
	A.assign(1, vector<int>(1));

	int res = 0;
	for (int16_t i = 1; i<N-1; i++) {
		for (int16_t j = 1; j<M-1; j++) {
			int16_t left = howFar[i][j+1][3], right = howFar[i][j-1][1];
			int16_t top = howFar[i+1][j][2], bottom = howFar[i-1][j][0];
 
			int16_t leftTop = howFar[i+1][left+1][2], leftBottom = howFar[i-1][left+1][0];
			int16_t rightTop = howFar[i+1][right-1][2], rightBottom = howFar[i-1][right-1][0];
 
			res += verify(top, int16_t(i+1), left, int16_t(j+1));
			res += verify(leftTop, int16_t(i+1), left, int16_t(j+1));
 
			res += verify(top, int16_t(i+1), int16_t(j-1), right);
			res += verify(rightTop, int16_t(i+1), int16_t(j-1), right);
 
 
			res += verify(int16_t(i-1), bottom, left, int16_t(j+1));
			res += verify(int16_t(i-1), leftBottom, left, int16_t(j+1));
 
			res += verify(int16_t(i-1), bottom, int16_t(j-1), right);
			res += verify(int16_t(i-1), rightBottom, int16_t(j-1), right);
		}
	}
	return res;
}
 
 
 
long long count_rectangles(std::vector<std::vector<int> > _a) {
	// cerr << "start\n";
	A = _a;
 
	N = A.size();
	M = A[0].size();
 
	makeHowFar();
	// cerr << "madehowfar\n";
 
	makeHowFarSegs();
	// cerr << "madesegs\n";
 
 
	int res = 0;
	vis.clear();
 
	res = makeCandidates();

	return res;
}

• 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: 28 / 28