Submission #1058902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058902		Tob	Rectangles (IOI19_rect)	C++14	0 / 100	241 ms	182548 KiB

rect

#include <bits/stdc++.h>

#include "rect.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 2507;
int b[N][N][4], h[N][N], res[N*N];
struct tri {
	int x, y, z, ix;
};
vector <tri> qu[N], qu2[N];

ll count_rectangles(vector <vector <int> > a) {
	int n = a.size(), m = a[0].size();
	for (int i = 0; i < n; i++) {
		stack <int> st;
		for (int j = 0; j < m; j++) {
			while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
			if (st.empty()) b[i][j][0] = -1;
			else b[i][j][0] = st.top();
			st.push(j);
		}
		while (!st.empty()) st.pop();
		for (int j = m-1; j >= 0; j--) {
			while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
			if (st.empty()) b[i][j][1] = -1;
			else b[i][j][1] = st.top();
			st.push(j);
		}
	}
	for (int j = 0; j < m; j++) {
		stack <int> st;
		for (int i = 0; i < n; i++) {
			while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
			if (st.empty()) b[i][j][2] = -1;
			else b[i][j][2] = st.top();
			st.push(i);
		}
		while (!st.empty()) st.pop();
		for (int i = n-1; i >= 0; i--) {
			while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
			if (st.empty()) b[i][j][3] = -1;
			else b[i][j][3] = st.top();
			st.push(i);
		}
	}
	
	for (int i = 1; i < n-1; i++) {
		for (int j = 1; j < m-1; j++) {
			int ok = 1;
			for (int k = 0; k < 4; k++) if (b[i][j][k] == -1) ok = 0;
			if (ok) {
				qu[b[i][j][3]-1].pb({b[i][j][0], b[i][j][1], b[i][j][2], i*m+j});
				qu2[b[i][j][1]-1].pb({b[i][j][2], b[i][j][3], b[i][j][0], i*m+j});
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i < n-1; i++) {
		for (int j = 1; j < m-1; j++) h[b[i-1][j][0]][b[i-1][j][1]] *= -1;
		for (int j = 1; j < m-1; j++) h[b[i][j][0]][b[i][j][1]] = -h[b[i][j][0]][b[i][j][1]]+1;
		for (int j = 1; j < m-1; j++) if (h[b[i-1][j][0]][b[i-1][j][1]] < 0) h[b[i-1][j][0]][b[i-1][j][1]] = 0;
		for (auto x : qu[i]) {
			if (i - x.z <= h[x.x][x.y]) res[x.ix]++;
		}
	}
	memset(h, 0, sizeof h);
	for (int j = 1; j < m-1; j++) {
		for (int i = 1; i < n-1; i++) h[b[i][j-1][2]][b[i][j-1][3]] *= -1;
		for (int i = 1; i < n-1; i++) h[b[i][j][2]][b[i][j][3]] = -h[b[i][j][2]][b[i][j][3]]+1;
		for (int i = 1; i < n-1; i++) if (h[b[i][j-1][0]][b[i][j-1][1]] < 0) h[b[i][j-1][0]][b[i][j-1][1]] = 0;
		for (auto x : qu2[j]) {
			if (j - x.z <= h[x.x][x.y]) res[x.ix]++;
		}
	}
	
	for (int i = 0; i < n*m; i++) cnt += res[i]/2;
	return cnt;
}
/*
int main() {
	int n, m; cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	long long result = count_rectangles(a);

	printf("%lld\n", result);
	return 0;
}*/

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