Submission #1282207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282207		PlayVoltz	Rectangles (IOI19_rect)	C++20	23 / 100	951 ms	256612 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

unordered_map<long long, bool> got;
vector<vector<int> > l, r, u, d, lu, ru, ul, dl;

void check(int x1, int x2, int y1, int y2){
	if (x1>x2||y1>y2)return;
	if (!(r[x2][y1-1]-1==y2&&ru[x2][y1-1]<=x1)&&!(l[x2][y2+1]+1==y1&&lu[x2][y2+1]<=x1))return;
	if (!(d[x1-1][y2]-1==x2&&dl[x1-1][y2]<=y1)&&!(u[x2+1][y2]+1==x1&&ul[x2+1][y2]<=y1))return;
	got[((x1*2505ll+y1)*2505ll+x2)*2505ll+y2]=1;
}

long long count_rectangles(vector<vector<int> > vect){
	int n=vect.size(), m=vect[0].size();
	l.assign(n, vector<int>(m, -1));
	r.assign(n, vector<int>(m, -1));
	u.assign(n, vector<int>(m, -1));
	d.assign(n, vector<int>(m, -1));
	lu.assign(n, vector<int>(m, -1));
	ru.assign(n, vector<int>(m, -1));
	ul.assign(n, vector<int>(m, -1));
	dl.assign(n, vector<int>(m, -1));
	for (int i=0; i<n; ++i){
		stack<int> st;
		for (int j=0; j<m; ++j){
			while (st.size()&&vect[i][st.top()]<vect[i][j])st.pop();
			if (st.size())l[i][j]=st.top();
			st.push(j);
		}
		while (st.size())st.pop();
		for (int j=m-1; j>=0; --j){
			while (st.size()&&vect[i][st.top()]<vect[i][j])st.pop();
			if (st.size())r[i][j]=st.top();
			st.push(j);
		}
	}
	for (int j=0; j<m; ++j){
		stack<int> st;
		for (int i=0; i<n; ++i){
			while (st.size()&&vect[st.top()][j]<vect[i][j])st.pop();
			if (st.size())u[i][j]=st.top();
			st.push(i);
		}
		while (st.size())st.pop();
		for (int i=n-1; i>=0; --i){
			while (st.size()&&vect[st.top()][j]<vect[i][j])st.pop();
			if (st.size())d[i][j]=st.top();
			st.push(i);
		}
	}
	for (int i=0; i<n; ++i)for (int j=0; j<m; ++j){
		if (l[i][j]!=-1){
			if (i&&l[i][j]==l[i-1][j])lu[i][j]=lu[i-1][j];
			else if (i&&r[i-1][l[i][j]]==j)lu[i][j]=ru[i-1][l[i][j]];
			else lu[i][j]=i;
		}
		if (r[i][j]!=-1){
			if (i&&r[i][j]==r[i-1][j])ru[i][j]=ru[i-1][j];
			else if (i&&l[i-1][r[i][j]]==j)ru[i][j]=lu[i-1][r[i][j]];
			else ru[i][j]=i;
		}
	}
	for (int j=0; j<m; ++j)for (int i=0; i<n; ++i){
		if (u[i][j]!=-1){
			if (j&&u[i][j]==u[i][j-1])ul[i][j]=ul[i][j-1];
			else if (j&&d[u[i][j]][j-1]==i)ul[i][j]=dl[u[i][j]][j-1];
			else ul[i][j]=j;
		}
		if (d[i][j]!=-1){
			if (j&&d[i][j]==d[i][j-1])dl[i][j]=dl[i][j-1];
			else if (j&&u[d[i][j]][j-1]==i)dl[i][j]=ul[d[i][j]][j-1];
			else dl[i][j]=j;
		}
	}
	for (int i=1; i<n-1; ++i)for (int j=1; j<m-1; ++j){
		if (u[i+1][j]!=-1&&l[i][j+1]!=-1)check(u[i+1][j]+1, i, l[i][j+1]+1, j);
		if (u[i+1][j]!=-1&&r[i][j-1]!=-1)check(u[i+1][j]+1, i, j, r[i][j-1]-1);
		if (d[i-1][j]!=-1&&l[i][j+1]!=-1)check(i, d[i-1][j]-1, l[i][j+1]+1, j);
		if (d[i-1][j]!=-1&&r[i][j-1]!=-1)check(i, d[i-1][j]-1, j, r[i][j-1]-1);
		if (d[i-1][j]!=-1&&l[d[i-1][j]][j+1]!=-1)check(i, d[i-1][j]-1, l[d[i-1][j]][j+1]+1, j);
		if (d[i-1][j]!=-1&&r[d[i-1][j]][j-1]!=-1)check(i, d[i-1][j]-1, j, r[d[i-1][j]][j-1]-1);
	}
	return (long long)got.size();
}

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