제출 #825897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825897		Josia	Rectangles (IOI19_rect)	C++17	10 / 100	5079 ms	621372 KiB

rect

// the edges are the walls!

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

using namespace std;

vector<vector<int>> A;
int N, M;

struct seg {
	vector<int> tree;
	bool minmax;
	int neut;

	int op(int a, int b) {
		if (minmax) return max(a,b);
		return min(a,b);
	}

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v] = x;
			return;
		}

		int rm = (rl + rr)/2;
		
		if (pos <= rm) update(v*2, rl, rm, pos, x);
		else update(v*2+1, rm+1, rr, pos, x);

		tree[v] = op(tree[v*2], tree[v*2+1]);
	}


	int query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return neut;
		if (rl == ql && rr == qr) return tree[v];

		int rm = (rl + rr) / 2;
		
		return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
	}

	void init(int n, vector<int> a, bool type) {
		minmax = type;
		if (type) neut = -1e9;
		else neut = 1e9;
		tree.assign(n*4, 0);


		for (int i = 0; i<n; i++) update(1, 0, n-1, i, a[i]);
	}
};


vector<vector<array<int, 4>>> howFar;	// 1,0; 0,1; -1,0; 0,-1;

void makeHowFar() {
	howFar.assign(N, vector<array<int, 4>>(M));
	for (int i = 0; i<N; i++) {
		set<pair<int, int>> s;
		for (int j = 0; j<M; j++) {
			while (s.size() && (*s.begin()).first <= A[i][j]) {
				howFar[i][(*s.begin()).second][1] = j;
				s.erase(s.begin());
			}
			s.insert({A[i][j], j});
		}
		for (auto aa: s) {
			howFar[i][aa.second][1] = M-1;
		}
	}

	for (int i = 0; i<M; i++) {
		set<pair<int, int>> s;
		for (int j = 0; j<N; j++) {
			while (s.size() && (*s.begin()).first <= A[j][i]) {
				howFar[(*s.begin()).second][i][0] = j;
				s.erase(s.begin());
			}
			s.insert({A[j][i], j});
		}
		for (auto aa: s) {
			howFar[aa.second][i][0] = N-1;
		}
	}

	for (int i = 0; i<N; i++) {
		set<pair<int, int>> s;
		for (int j = M-1; j>=0; j--) {
			while (s.size() && (*s.begin()).first <= A[i][j]) {
				howFar[i][(*s.begin()).second][3] = j;
				s.erase(s.begin());
			}
			s.insert({A[i][j], j});
		}
		for (auto aa: s) {
			howFar[i][aa.second][3] = 0;
		}
	}

	for (int i = 0; i<M; i++) {
		set<pair<int, int>> s;
		for (int j = N-1; j>=0; j--) {
			while (s.size() && (*s.begin()).first <= A[j][i]) {
				howFar[(*s.begin()).second][i][2] = j;
				s.erase(s.begin());
			}
			s.insert({A[j][i], j});
		}
		for (auto aa: s) {
			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);
	}
}


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(1, 0, M-1, left+1, right-1) >= bottom)) return 0;
	if(!(howFar_10[bottom].query(1, 0, M-1, left+1, right-1) <= top)) return 0;

	if(!(howFar01[left].query(1, 0, N-1, top+1, bottom-1) >= right)) return 0;
	if(!(howFar0_1[right].query(1, 0, N-1, top+1, bottom-1) <= left)) return 0;

	return 1;
}



set<array<int,4>> candidates;



void makeCandidates() {
	for (int i = 1; i<N-1; i++) {
		for (int j = 1; j<M-1; j++) {
			int left = howFar[i][j+1][3], right = howFar[i][j-1][1];
			int top = howFar[i+1][j][2], bottom = howFar[i-1][j][0];

			int leftTop = howFar[i+1][left][2], leftBottom = howFar[i-1][left][0];
			int rightTop = howFar[i+1][right][2], rightBottom = howFar[i-1][right][0];

			candidates.insert({top, i+1, left, j+1});
			candidates.insert({leftTop, i+1, left, j+1});

			candidates.insert({top, i+1, j-1, right});
			candidates.insert({rightTop, i+1, j-1, right});


			candidates.insert({i-1, bottom, left, j+1});
			candidates.insert({i-1, leftBottom, left, j+1});

			candidates.insert({i-1, bottom, j-1, right});
			candidates.insert({i-1, rightBottom, j-1, right});
		}
	}
}





long long count_rectangles(std::vector<std::vector<int> > _a) {
	A = _a;

	N = A.size();
	M = A[0].size();

	makeHowFar();

	// for (auto i: howFar) {
	// 	for (auto j: i) {
	// 		for (int k: j) cerr<<k<<",";
	// 		cerr << " ";
	// 	}
	// 	cerr << "\n";
	// }

	makeHowFarSegs();

	int res = 0;

	makeCandidates();

	for (auto i: candidates) {
		res += verify(i[0], i[1], i[2], i[3]);
		// if (verify(i[0], i[1], i[2], i[3])) cerr << i[0]+1 << " " << i[1]-1 << " " << i[2]+1 << " " << i[3]-1 << "\n";
	}

	// for (int i = 0; i<N; i++) {
	// 	for (int j = 0; j<M; j++) {
	// 		for (int k = 0; k<N; k++) {
	// 			for (int l = 0; l<M; l++) {
	// 				res += verify(i,k,j,l);
	// 			}
	// 		}
	// 	}
	// }


	return res;
}

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