Submission #1103875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103875		_8_8_	Rectangles (IOI19_rect)	C++17	72 / 100	5094 ms	909872 KiB

rect

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

using namespace std;
typedef long long ll;

const int N = 2500 + 12;
int n, m, a[N][N], it[N][N];
vector<array<int, 2>> r[N];
vector<int> id[N][N], t[N][N], f[N][N];
void prec() {
	for(int i = 2; i < n; i++) {
		vector<int> st;
		for(int j = 1; j <= m; j++) {
			while(!st.empty() && a[i][st.back()] < a[i][j]) {
				st.pop_back();
			} 
			if(!st.empty()) {
				int l = st.back();
				if(l + 1 <= j - 1) {
					r[i].push_back({l + 1, j - 1});
				}
			}
			st.push_back(j);
		}
		st.clear();
		for(int j = m; j >= 1; j--) {
			while(!st.empty() && a[i][st.back()] < a[i][j]) {
				st.pop_back();
			}
			if(!st.empty()) {
				int l = st.back();
				if(j + 1 <= l - 1) {
					r[i].push_back({j + 1, l - 1});
				}
			}
			st.push_back(j);
		}
		sort(r[i].begin(), r[i].end());
		r[i].resize(unique(r[i].begin(), r[i].end()) - r[i].begin());
		for(auto [l, r]:r[i]) {
			id[l][r].push_back(i);
		}
	}
	for(int j = 2; j < m; j++) {
		vector<int> st;
		for(int i = 1; i <= n; i++) {
			while(!st.empty() && a[st.back()][j] < a[i][j]) {
				st.pop_back();
			}
			if(!st.empty()) {
				int l = st.back();
				if(l + 1 <= i - 1) {
					t[l + 1][j].push_back(i - 1);
				}
			}
			st.push_back(i);
		}
		st.clear();
		for(int i = n; i >= 1; i--) {
			while(!st.empty() && a[st.back()][j] < a[i][j]) {
				st.pop_back();
			}
			if(!st.empty()) {
				int l = st.back();
				if(l - 1 >= i + 1) {
					t[i + 1][j].push_back(l - 1);
				}
			}
			st.push_back(i);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			sort(t[i][j].begin(), t[i][j].end());
			t[i][j].resize(unique(t[i][j].begin(), t[i][j].end()) - t[i][j].begin());
		}
	}
	for(int i = 1; i <= m; i++) {
		for(int j = i; j <= m; j++) {
			f[i][j].resize((int)id[i][j].size());
			for(int k = 0; k < (int)f[i][j].size(); k++) {
				if(k && id[i][j][k] - 1 == id[i][j][k - 1]) {
					f[i][j][k] = f[i][j][k - 1];
				} else {
					int it = k + 1;
					while(it < (int)id[i][j].size() && id[i][j][it] - 1 == id[i][j][it - 1]) {
						it++;
					}
					it--;
					f[i][j][k] = id[i][j][it];
				}
			}
		}
	}
}
ll solve() {
	ll res = 0;
	for(int i = 2; i < n; i++) {
		vector<array<int, 2>> pt;
		for(int j = 2; j < m; j++) {
			for(int f:t[i][j]) {
				pt.push_back({f, j});
			}
		}
		sort(pt.begin(), pt.end());
		vector<array<int, 3>> s;
		for(int i = 0; i < (int)pt.size(); ) {
			int j = i + 1;
			while(j < (int)pt.size() && pt[j][0] == pt[j - 1][0] && pt[j][1] == pt[j - 1][1] + 1) {
				j++;
			}
			s.push_back({pt[i][0], pt[i][1], pt[j - 1][1]});
			i = j;
		}
		for(auto [l, r]:r[i]) {
			for(auto [g, L, R]:s) {
				if(L <= l && R >= r && g <= f[l][r][it[l][r]]) {
					res++;
				}
			}
		}
		for(auto [l, r]:r[i]) {
			it[l][r]++;
		}
	}

	return res;
}
ll count_rectangles(vector<vector<int> > _A) {
	n = (int)_A.size();
	m = (int)_A[0].size();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] = _A[i - 1][j - 1];
		}
	}
	prec();
	return solve();
}

• 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