Submission #924701

#	Time	Username	Problem	Language	Result	Execution time	Memory
924701		byunjaewoo	Rectangles (IOI19_rect)	C++17	72 / 100	5064 ms	547736 KiB

rect

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

const int Nmax=2510;
int N, M, A[Nmax][Nmax], L[Nmax][Nmax], R[Nmax][Nmax], D[Nmax][Nmax], U[Nmax][Nmax];
vector<tuple<int, int, int, int>> X, Y;

ll count_rectangles(vector<vector<int> > a) {
	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];
	for(int i=1; i<=N; i++) {
		stack<pair<int, int>> S;
		for(int j=1; j<=M; j++) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) L[i][j]=S.top().second;
			S.push({A[i][j], j});
		}
		while(!S.empty()) S.pop();
		for(int j=M; j>=1; j--) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) R[i][j]=S.top().second;
			S.push({A[i][j], j});
		}
	}
	for(int j=1; j<=M; j++) {
		stack<pair<int, int>> S;
		for(int i=1; i<=N; i++) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) U[i][j]=S.top().second;
			S.push({A[i][j], i});
		}
		while(!S.empty()) S.pop();
		for(int i=N; i>=1; i--) {
			while(!S.empty() && S.top().first<=A[i][j]) S.pop();
			if(!S.empty()) D[i][j]=S.top().second;
			S.push({A[i][j], i});
		}
	}
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
		if(L[i][j] && R[i][j]) X.push_back({L[i][j]+1, R[i][j]-1, i, i});
		if(U[i][j] && D[i][j]) Y.push_back({U[i][j]+1, D[i][j]-1, j, j});
	}
	sort(X.begin(), X.end()), sort(Y.begin(), Y.end());
	X.erase(unique(X.begin(), X.end()), X.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for(int i=(int)X.size()-2; i>=0; i--) {
		auto [l, r, y, v]=X[i];
		auto [ll, rr, yy, vv]=X[i+1];
		if(l==ll && r==rr && y+1==yy) X[i]={l, r, y, vv};
	}
	for(int i=(int)Y.size()-2; i>=0; i--) {
		auto [l, r, x, v]=Y[i];
		auto [ll, rr, xx, vv]=Y[i+1];
		if(l==ll && r==rr && x+1==xx) Y[i]={l, r, x, vv};
	}
	vector<tuple<int, int, int, int>>  ret;
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
		if(!L[i][j] || !R[i][j] || !U[i][j] || !D[i][j]) continue;
		auto p=lower_bound(X.begin(), X.end(), make_tuple(L[i][j]+1, R[i][j]-1, U[i][j]+1, 0));
		if(p==X.end()) continue;
		auto [l, r, y, v]=(*p);
		if(l!=L[i][j]+1 || r!=R[i][j]-1 || y!=U[i][j]+1 || v<D[i][j]-1) continue;
		auto q=lower_bound(Y.begin(), Y.end(), make_tuple(U[i][j]+1, D[i][j]-1, L[i][j]+1, 0));
		if(q==Y.end()) continue;
		auto [ll, rr, xx, vv]=(*q);
		if(ll!=U[i][j]+1 || rr!=D[i][j]-1 || xx!=L[i][j]+1 || vv<R[i][j]-1) continue;
		ret.push_back({L[i][j], R[i][j], U[i][j], D[i][j]});
	}
	sort(ret.begin(), ret.end());
	ret.erase(unique(ret.begin(), ret.end()), ret.end());
	return ret.size();
}

• 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