제출 #1222672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222672		HappyCapybara	Rectangles (IOI19_rect)	C++17	100 / 100	4905 ms	771480 KiB

rect

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

#pragma GCC optimize("O3")

#define ll long long

ll f(ll a, ll b, ll c, ll d){
	return a+b*(ll)2500+c*(ll)pow(2500, 2)+d*(ll)pow(2500, 3);
}

ll count_rectangles(vector<vector<int>> a){
	//cout << 1 << endl;
	int n = a.size(), m = a[0].size();
	vector<vector<int>> l(n, vector<int>(m, -1)), r(n, vector<int>(m, -1)), u(n, vector<int>(m, -1)), d(n, vector<int>(m, -1));
	stack<pair<int,int>> st;
	for (int i=0; i<n; i++){
		while (!st.empty()) st.pop();
		for (int j=0; j<m; j++){
			while (!st.empty() && st.top().first <= a[i][j]){
				r[i][st.top().second] = j;
				if (st.top().first == a[i][j]) l[i][j] = st.top().second;
				st.pop();
			}
			if (!st.empty() && l[i][j] == -1) l[i][j] = st.top().second;
			st.push({a[i][j], j});
		}
	}
	for (int j=0; j<m; j++){
		while (!st.empty()) st.pop();
		for (int i=0; i<n; i++){
			while (!st.empty() && st.top().first <= a[i][j]){
				d[st.top().second][j] = i;
				if (st.top().first == a[i][j]) u[i][j] = st.top().second;
				st.pop();
			}
			if (!st.empty() && u[i][j] == -1) u[i][j] = st.top().second;
			st.push({a[i][j], i});
		}
	}
	//cout << 2 << endl;
	vector<vector<int>> ld(n, vector<int>(m, 0)), rd(n, vector<int>(m, 0)), ud(n, vector<int>(m, 0)), dd(n, vector<int>(m, 0));
	for (int i=n-1; i>=0; i--){
		for (int j=0; j<m; j++){
			if (l[i][j] != -1){
				ld[i][j] = 1;
				if (i != n-1){
					if (l[i+1][j] == l[i][j]) ld[i][j] = 1+ld[i+1][j];
					if (r[i+1][l[i][j]] == j) ld[i][j] = 1+rd[i+1][l[i][j]];
				}
			}
			if (r[i][j] != -1){
				rd[i][j] = 1;
				if (i != n-1){
					if (r[i+1][j] == r[i][j]) rd[i][j] = 1+rd[i+1][j];
					if (l[i+1][r[i][j]] == j) rd[i][j] = 1+ld[i+1][r[i][j]];
				}
			}
		}
	}
	for (int j=m-1; j>=0; j--){
		for (int i=0; i<n; i++){
			if (d[i][j] != -1){
				dd[i][j] = 1;
				if (j != m-1){
					if (d[i][j+1] == d[i][j]) dd[i][j] = 1+dd[i][j+1];
					if (u[d[i][j]][j+1] == i) dd[i][j] = 1+ud[d[i][j]][j+1];
				}
			}
			if (u[i][j] != -1){
				ud[i][j] = 1;
				if (j != m-1){
					if (u[i][j+1] == u[i][j]) ud[i][j] = 1+ud[i][j+1];
					if (d[u[i][j]][j+1] == i) ud[i][j] = 1+dd[u[i][j]][j+1];
				}
			}
		}
	}
	//cout << 3 << endl;
	vector<ll> cand;
	for (int i=1; i<n-1; i++){
		for (int j=1; j<m-1; j++){
			if (r[i][j-1] != -1){
				if (d[i-1][r[i][j-1]-1] != -1) cand.push_back(f(i, d[i-1][r[i][j-1]-1]-1, j, r[i][j-1]-1));
				if (u[i+1][r[i][j-1]-1] != -1) cand.push_back(f(u[i+1][r[i][j-1]-1]+1, i, j, r[i][j-1]-1));
				if (d[i-1][j] != -1) cand.push_back(f(i, d[i-1][j]-1, j, r[i][j-1]-1));
				if (u[i+1][j] != -1) cand.push_back(f(u[i+1][j]+1, i, j, r[i][j-1]-1));
			}
			if (l[i][j+1] != -1){
				if (d[i-1][l[i][j+1]+1] != -1) cand.push_back(f(i, d[i-1][l[i][j+1]+1]-1, l[i][j+1]+1, j));
				if (u[i+1][l[i][j+1]+1] != -1) cand.push_back(f(u[i+1][l[i][j+1]+1]+1, i, l[i][j+1]+1, j));
				if (d[i-1][j] != -1) cand.push_back(f(i, d[i-1][j]-1, l[i][j+1]+1, j));
				if (u[i+1][j] != -1) cand.push_back(f(u[i+1][j]+1, i, l[i][j+1]+1, j));
			}
			/*if (d[i-1][j] != -1){
				if (r[d[i-1][j]-1][j-1] != -1) cand.push_back(f(i, d[i-1][j]-1, j, r[d[i-1][j]-1][j-1]-1));
				if (l[d[i-1][j]-1][j+1] != -1) cand.push_back(f(i, d[i-1][j]-1, l[d[i-1][j]-1][j+1]+1, j));
				if (r[i][j-1] != -1) cand.push_back(f(i, d[i-1][j]-1, j, r[i][j-1]-1));
				if (l[i][j+1] != -1) cand.push_back(f(i, d[i-1][j]-1, l[i][j+1]+1, j));
			}*/
			/*if (u[i+1][j] != -1){
				if (r[u[i+1][j]+1][j-1] != -1) cand.push_back(f(u[i+1][j]+1, i, j, r[u[i+1][j]+1][j-1]-1));
				if (l[u[i+1][j]+1][j+1] != -1) cand.push_back(f(u[i+1][j]+1, i, l[u[i+1][j]+1][j+1]+1, j));
				if (r[i][j-1] != -1) cand.push_back(f(u[i+1][j]+1, i, j, r[i][j-1]-1));
				if (l[i][j+1] != -1) cand.push_back(f(u[i+1][j]+1, i, l[i][j+1]+1, j));
			}*/
		}
	}
	//cout << 4 << endl;
	ll res = 0;
	sort(cand.begin(), cand.end());
	for (int z=0; z<(int)cand.size(); z++){
		if (z && cand[z] == cand[z-1]) continue;
		ll v = cand[z];
		int t = v % 2500, b = (v/(ll)2500) % 2500, i = (v/(ll)pow(2500, 2)) % 2500, j = (v/(ll)pow(2500, 3)) % 2500;
		if (b < t || j < i) continue;
		if (((r[t][i-1] == j+1 && rd[t][i-1] > b-t) || (l[t][j+1] == i-1 && ld[t][j+1] > b-t)) && ((d[t-1][i] == b+1 && dd[t-1][i] > j-i) || (u[b+1][i] == t-1 && ud[b+1][i] > j-i))) res++;
	}
	//cout << 5 << endl;
	return res;
}

• 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