Submission #702366

#	Time	Username	Problem	Language	Result	Execution time	Memory
702366		onjo0127	Rectangles (IOI19_rect)	C++17	23 / 100	951 ms	629408 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int _N = 2555;

int A[_N][_N], L[_N][_N], R[_N][_N], U[_N][_N], D[_N][_N], IU[_N][_N], IL[_N][_N];
vector<pii> IR[_N][_N], ID[_N][_N];

long long count_rectangles(vector<vector<int>> a) {
	int N = a.size(), M = 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];
	vector<int> S;
	for(int i=1; i<=N; i++) {
		S = {1};
		for(int j=2; j<=M; j++) {
			while(S.size() && A[i][S.back()] < A[i][j]) {
				R[i][S.back()] = j;
				S.pop_back();
			}
			S.push_back(j);
		}
		while(S.size()) {
			R[i][S.back()] = M+1;
			S.pop_back();
		}
		S = {M};
		for(int j=M-1; j>=1; j--) {
			while(S.size() && A[i][S.back()] <= A[i][j]) {
				L[i][S.back()] = j;
				S.pop_back();
			}
			S.push_back(j);
		}
	}
	for(int j=1; j<=M; j++) {
		S = {1};
		for(int i=2; i<=N; i++) {
			while(S.size() && A[S.back()][j] < A[i][j]) {
				D[S.back()][j] = i;
				S.pop_back();
			}
			S.push_back(i);
		}
		while(S.size()) {
			D[S.back()][j] = N+1;
			S.pop_back();
		}
		S = {N};
		for(int i=N-1; i>=1; i--) {
			while(S.size() && A[S.back()][j] <= A[i][j]) {
				U[S.back()][j] = i;
				S.pop_back();
			}
			S.push_back(i);
		}
	}
	auto fnd = [&](vector<pii> &S, int v) {
		int p = lower_bound(S.begin(), S.end(), make_pair(v, 0)) - S.begin();
		if(p < S.size() && S[p].first == v) return S[p].second;
		return 0;
	};
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=M; j++) {
			if(1 <= L[i][j] && R[i][j] <= M && A[i][L[i][j]] > A[i][j]) {
				IU[i][j] = i;
				int v = fnd(IR[i-1][L[i][j]], R[i][j]);
				if(v) IU[i][j] = v;
				IR[i][L[i][j]].push_back({R[i][j], IU[i][j]});
			}
			if(1 <= U[i][j] && D[i][j] <= N && A[U[i][j]][j] > A[i][j]) {
				IL[i][j] = j;
				int v = fnd(ID[U[i][j]][j-1], D[i][j]);
				if(v) IL[i][j] = v;
				ID[U[i][j]][j].push_back({D[i][j], IL[i][j]});
			}
		}
	}
	long long ans = 0;
	for(int i=2; i<N; i++) {
		for(int j=2; j<M; j++) {
			if(IU[i][j] && IL[i][j]) {
				//int vu = fnd(IR[D[i][j] - 1][L[i][j]], R[i][j]), vl = fnd(ID[U[i][j]][R[i][j] - 1], D[i][j]);
				//if(vu && vu <= U[i][j] + 1 && vl && vl <= L[i][j] + 1) ++ans;
				bool ok = 1;
				for(int a=U[i][j]+1; a<D[i][j]; a++) {
					for(int b=L[i][j]+1; b<R[i][j]; b++) {
						if(A[a][b] >= min({A[a][L[i][j]], A[a][R[i][j]], A[U[i][j]][b], A[D[i][j]][b]})) ok = 0;
					}
				}
				if(ok) ++ans;
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:60:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if(p < S.size() && S[p].first == v) return S[p].second;
      |      ~~^~~~~~~~~~

• 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