Submission #424907

#	Time	Username	Problem	Language	Result	Execution time	Memory
424907		amoo_safar	Rectangles (IOI19_rect)	C++17	0 / 100	883 ms	987592 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef pair<int, int> pii;

const int N = 2510;

struct Maximal {
	vector<int> A, L, R;
	void Add(int x){
		A.pb(x);
	}
	void Init(){
		sort(all(A));
		A.resize( unique(all(A)) - A.begin());

		L.resize(A.size(), 0);
		for(int i = 1; i < (int) A.size(); i++)
			L[i] = (A[i - 1] + 1 == A[i] ? L[i - 1] + 1 : 0);
		R.resize(A.size(), 0);
		for(int i = ((int)A.size()) - 2; i >= 0; i--)
			R[i] = (A[i] + 1 == A[i + 1] ? R[i + 1] + 1 : 0);
	}
	pii Get(int x){
		int idx = lower_bound(all(A), x) - A.begin();
		assert(A[idx] == x);
		return pii(L[idx], R[idx]);
	}
};
Maximal row[N][N], col[N][N];

int L[N][N], R[N][N], U[N][N], D[N][N];

long long count_rectangles(vector< vector<int> > a){
	int n = a.size();
	int m = a[0].size();
	for(int i = 0; i < N; i++){
		fill(L[i], L[i] + N, -1);
		fill(R[i], R[i] + N,  m);
		fill(U[i], U[i] + N, -1);
		fill(D[i], D[i] + N,  n);
	}
	vector<int> stk;

	for(int i = 0; i < n; i++){
		stk.clear();
		for(int j = 0; j < m; j++){
			while(!stk.empty() && a[i][stk.back()] <= a[i][j]){
				R[i][stk.back()] = j;
				stk.pop_back();
			}
			if(!stk.empty())
				L[i][j] = stk.back();
			stk.pb(j);
		}
	}
	for(int j = 0; j < m; j++){
		stk.clear();
		for(int i = 0; i < n; i++){
			while(!stk.empty() && a[stk.back()][j] <= a[i][j]){
				D[stk.back()][j] = i;
				stk.pop_back();
			}
			if(!stk.empty())
				U[i][j] = stk.back();
			stk.pb(i);
		}
	}
	// debug("A");
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(L[i][j] != -1)
				row[ L[i][j] ][j].Add(i);
			if(R[i][j] != m)
				row[j][ R[i][j] ].Add(i);
			
			if(U[i][j] != -1)
				col[ U[i][j] ][i].Add(j);
			if(D[i][j] != n)
				col[i][ D[i][j] ].Add(j);
		}
	}
	// debug("B");
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			row[i][j].Init(), col[i][j].Init();
	// debug("C");
	vector< pair<pii, pii> > valid;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(L[i][j] == -1 || U[i][j] == -1 || R[i][j] == m || D[i][j] == n)
				continue;
			pii rw = pii(L[i][j], R[i][j]);
			pii cl = pii(U[i][j], D[i][j]);
			pii grw= row[rw.F][rw.S].Get(i);
			pii gcl= col[cl.F][cl.S].Get(j);
			if((i - grw.F <= cl.F + 1) && (cl.S -1 <= i + grw.S))
				if((j - gcl.F <= rw.F + 1) && (rw.S - 1 <= j + gcl.S))
					valid.pb({rw, cl});
		}
	}

	sort(all(valid));
	valid.resize( unique(all(valid)) - valid.begin() );
	return valid.size();
}

• 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