Submission #390346

#	Time	Username	Problem	Language	Result	Execution time	Memory
390346		SuhaibSawalha1	Rectangles (IOI19_rect)	C++17	50 / 100	5069 ms	686788 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> lg{-1};
 
struct RMQ {
	vector<vector<array<int, 2>>> sp;
	void init (vector<array<int, 2>> &a) {
		int n = a.size();
		sp.resize(lg[n]+1, vector<array<int, 2>>(n));
		sp[0] = a;
		for (int i = 1; i < lg[n]+1; ++i) {
			for (int j = 0; j < n - (1 << i) + 1; ++j) {
				sp[i][j][0] = max(sp[i - 1][j][0], sp[i - 1][j + (1 << (i - 1))][0]);
				sp[i][j][1] = max(sp[i - 1][j][1], sp[i - 1][j + (1 << (i - 1))][1]);
			}
		}
	}
	int query (int l, int r, int i) {
		int k = lg[r-l+1];
		return max(sp[k][l][i], sp[k][r - (1 << k) + 1][i]);
	}
};

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	int left[n][m], right[n][m];
	for (int i = 0; i < n; ++i) {
		stack<int> st;
		for (int j = 0; j < m; ++j) {
			while (st.size() && a[i][st.top()] < a[i][j]) {
				st.pop();
			}
			left[i][j] = st.size() ? st.top() + 1 : 0;
			st.push(j);
		}
	}
	for (int i = 0; i < n; ++i) {
		stack<int> st;
		for (int j = m - 1; ~j; --j) {
			while (st.size() && a[i][st.top()] < a[i][j]) {
				st.pop();
			}
			right[i][j] = st.size() ? st.top() - 1 : m - 1;
			st.push(j);
		}
	}
	for (int i = 1; i <= n; ++i) {
		lg.push_back(lg.back()+!(i&(i-1)));
	}
	RMQ col[m];
	for (int j = 0; j < m; ++j) {
		vector<array<int, 2>> p(n);
		for (int i = 0; i < n; ++i) {
			p[i] = {a[i][j], left[i][j]};
		}
		col[j].init(p);
	}
	long long ans = 0;
	for (int x = 1; x < n - 1; ++x) {
		for (int y = 1; y < m - 1; ++y) {
			int M = 1e9;
			for (int i = x; i < n  - 1; ++i) {
				if (a[i][y] >= a[i][y - 1] || a[i][y] >= a[x - 1][y]) {
					break;
				}
				M = min(M, right[i][y - 1]);
				bool bad = 0;
				int limit = min(m - 1, M + 1);
				for (int j = y; j < limit && !bad; ++j) {
					int mx = col[j].query(x, i, 0);
					bad |= mx >= a[x - 1][j] || mx >= a[i + 1][j];
					ans += col[j + 1].query(x, i, 1) <= y && mx < a[i + 1][j] && mx < a[x - 1][j];
				}
			}
		}
	}
	return ans;
}

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