Submission #810405

#	Time	Username	Problem	Language	Result	Execution time	Memory
810405		NothingXD	Rectangles (IOI19_rect)	C++17	100 / 100	2482 ms	728616 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail> 
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 3e3 + 10;
const int lg = 20;

int n, m, spt[lg][maxn], a[maxn][maxn], l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn], ans[maxn][maxn];
int L[maxn][maxn], R[maxn][maxn], U[maxn][maxn], D[maxn][maxn];
vector<pii> Q[maxn][4];

struct rect{
	int a, b, c, d;
};

int getmin(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	return min(spt[x][l], spt[x][r-(1<<x)]);
}

int getmax(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	return max(spt[x][l], spt[x][r-(1<<x)]);
}

ll count_rectangles(vector<vector<int>> A) {
	n = A.size();
	m = A[0].size();
	//debug(n, m);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			a[i][j] = A[i][j];
			//		debug(i, j, a[i][j]);
		}
	}
	//	debug(1);
	for (int i = 0; i < n; i++){
		vector<int> v;
		for (int j = 0; j < m; j++){
			l[i][j] = -1;
			while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
			if (!v.empty()) l[i][j] = v.back();
			v.push_back(j);
		}
		v.clear();
		for (int j = m-1; ~j; j--){
			r[i][j] = m;
			while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
			if (!v.empty()){
				r[i][j] = v.back();
				//	debug(i, j, v.back(), a[i][j], a[i][v.back()]);
			}
			v.push_back(j);
		}
	}
	//	debug(2);
	for (int j = 0; j < m; j++){
		vector<int> v;
		for (int i = 0; i < n; i++){
			u[i][j] = -1;
			while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
			if (!v.empty()) u[i][j] = v.back();
			v.push_back(i);
		}
		v.clear();
		for (int i = n-1; ~i; i--){
			d[i][j] = n;
			while (!v.empty() && a[v.back()][j] <= a[i][j]){
				//debug(i, j, v.back(), a[v.back()][j], a[i][j]);
				v.pop_back();
			}
			if (!v.empty()) d[i][j] = v.back();
			v.push_back(i);
		}
	}
	//	debug(3);
	for (int x = 0; x < n; x++){
		for (int y = 0; y < m; y++){
			//			debug(x, y, l[x][y], r[x][y], u[x][y], d[x][y]);
			if (l[x][y] == -1 || r[x][y] == m || d[x][y] == n || u[x][y] == -1) continue;
			//			debug(1);
			Q[l[x][y]][0].push_back({x, y});
			Q[r[x][y]][1].push_back({x, y});
			Q[u[x][y]][2].push_back({x, y});
			Q[d[x][y]][3].push_back({x, y});
		}
	}
	for (int i = 0; i < n; i++){
		vector<int> v;
		for (int j = 0; j < m; j++){
			L[i][j] = -1;
			while (!v.empty() && a[i][v.back()] < a[i][j]) v.pop_back();
			if (!v.empty()) L[i][j] = v.back();
			v.push_back(j);
		}
		v.clear();
		for (int j = m-1; ~j; j--){
			R[i][j] = m;
			while (!v.empty() && a[i][v.back()] < a[i][j]) v.pop_back();
			if (!v.empty()){
				R[i][j] = v.back();
				//	debug(i, j, v.back(), a[i][j], a[i][v.back()]);
			}
			v.push_back(j);
		}
	}
	//	debug(2);
	for (int j = 0; j < m; j++){
		vector<int> v;
		for (int i = 0; i < n; i++){
			U[i][j] = -1;
			while (!v.empty() && a[v.back()][j] < a[i][j]) v.pop_back();
			if (!v.empty()) U[i][j] = v.back();
			v.push_back(i);
		}
		v.clear();
		for (int i = n-1; ~i; i--){
			D[i][j] = n;
			while (!v.empty() && a[v.back()][j] < a[i][j]){
				//debug(i, j, v.back(), a[v.back()][j], a[i][j]);
				v.pop_back();
			}
			if (!v.empty()) D[i][j] = v.back();
			v.push_back(i);
		}
	}


	//	debug(4);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			spt[0][j] = U[i][j];
		}
		for (int j = 1; j < lg; j++){
			for (int k = 0; k + (1 << j) <= m; k++){
				spt[j][k] = max(spt[j-1][k], spt[j-1][k+(1<<(j-1))]);
			}
		}
		for (auto [x, y]: Q[i][3]){
			if (getmax(l[x][y]+1, r[x][y]-1) <= u[x][y]) ans[x][y]++;
		}
		for (int j = 0; j < m; j++){
			spt[0][j] = D[i][j];
		}
		for (int j = 1; j < lg; j++){
			for (int k = 0; k + (1 << j) <= m; k++){
				spt[j][k] = min(spt[j-1][k], spt[j-1][k+(1<<(j-1))]);
			}
		}
		for (auto [x, y]: Q[i][2]){
			if (getmin(l[x][y]+1, r[x][y]-1) >= d[x][y]) ans[x][y]++;
		}
	}
	//	debug(5);
	for (int j = 0; j < m; j++){
		//		debug(j);
		for (int i = 0; i < n; i++){
			spt[0][i] = L[i][j];
		}
		for (int i = 1; i < lg; i++){
			for (int k = 0; k + (1 << i) <= n; k++){
				spt[i][k] = max(spt[i-1][k], spt[i-1][k+(1<<(i-1))]);
			}
		}
		//		debug(1);
		for (auto [x, y]: Q[j][1]){
			if (getmax(u[x][y]+1, d[x][y]-1) <= l[x][y]) ans[x][y]++;
		}
		//		debug(2);
		for (int i = 0; i < n; i++){
			spt[0][i] = R[i][j];
		}
		for (int i = 1; i < lg; i++){
			for (int k = 0; k + (1 << i) <= n; k++){
				spt[i][k] = min(spt[i-1][k], spt[i-1][k+(1<<(i-1))]);
			}
		}
		//	debug(3);
		for (auto [x, y]: Q[j][0]){
			if (getmin(u[x][y]+1, d[x][y]-1) >= r[x][y]) ans[x][y]++;
		}
		//	debug(4);
	}
	vector<pair<pii,pii>> res;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (ans[i][j] == 4) res.push_back({{l[i][j]+1, r[i][j]-1}, {u[i][j]+1, d[i][j]-1}});
		}
	}
	sort(all(res));
	res.resize(distance(res.begin(), unique(all(res))));
	/*for (auto [a, b]: res){
		debug(a.F, a.S, b.F, b.S);
	}*/
	return res.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: 28 / 28