Submission #1058986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058986		Tob	Rectangles (IOI19_rect)	C++14	100 / 100	2571 ms	807248 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);
		}
	}
	
	auto good = [&](int x, int y, int o) {return b[x][y][2*o] != -1 && b[x][y][2*o+1] != -1;};
	
	for (int i = 1; i < n-1; i++) {
		for (int j = 1; j < m-1; j++) {
			if (good(i, j, 0) && good(i, j, 1)) {
				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++) if (good(i-1, j, 0) && h[b[i-1][j][0]][b[i-1][j][1]] >= 0) h[b[i-1][j][0]][b[i-1][j][1]] *= -1;
		for (int j = 1; j < m-1; j++) if (good(i, j, 0) && h[b[i][j][0]][b[i][j][1]] <= 0) 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 (good(i-1, j, 0) && 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++) if (good(i, j-1, 1) && h[b[i][j-1][2]][b[i][j-1][3]] >= 0) h[b[i][j-1][2]][b[i][j-1][3]] *= -1;
		for (int i = 1; i < n-1; i++) if (good(i, j, 1) && h[b[i][j][2]][b[i][j][3]] <= 0) 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 (good(i, j-1, 1)) if (h[b[i][j-1][2]][b[i][j-1][3]] < 0) h[b[i][j-1][2]][b[i][j-1][3]] = 0;
		for (auto x : qu2[j]) {
			if (j - x.z <= h[x.x][x.y]) res[x.ix]++;
		}
	}
	
	map <ll, int> ma;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (res[i*m+j] == 2) {
				ll en = 0;
				for (int k = 0; k < 4; k++) en = (en << 16) + b[i][j][k];
				cnt += !ma[en];
				ma[en] = 1;
			}
		}
	}
	
	return cnt;
}

• 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