Submission #295324

#	Time	Username	Problem	Language	Result	Execution time	Memory
295324		Atill83	Rectangles (IOI19_rect)	C++14	50 / 100	1008 ms	463224 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (int) 205;

bool hori[MAXN][MAXN][MAXN], verti[MAXN][MAXN][MAXN];
int ph[MAXN][MAXN][MAXN], pv[MAXN][MAXN][MAXN];
int nx[2505];
ll pre[2505][2505];
bool visited[2505][2505];
int mxx[4'250'050], mxy[4'250'050], mnx[4'250'050], mny[4'250'050];
int cc = 0;
void dfs(int i, int j, vector<vector<int>> &vc){
	if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
		return;
	}
	if(visited[i][j]) return;
	visited[i][j] = 1;
	mnx[cc] = min(mnx[cc], i);
	mxx[cc] = max(mxx[cc], i);
	mny[cc] = min(mny[cc], j);
	mxy[cc] = max(mxy[cc], j);
	dfs(i + 1, j, vc);
	dfs(i - 1, j, vc);
	dfs(i, j + 1, vc);
	dfs(i, j - 1, vc);
}

int gtpre(int x1, int y1, int x2, int y2){
	if(x1 == 0 && y1 == 0){
		return pre[x2][y2];
	}else if(x1 == 0){
		return pre[x2][y2] - pre[x2][y1 - 1];
	}else if(y1 == 0){
		return pre[x2][y2] - pre[x1 - 1][y2];
	}else{
		return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
	}
}


long long count_rectangles(vector<vector<int>> a) {
	ll ans = 0;
	int n = a.size();
	int m = a[0].size();
	if(n <= 200 && m <= 200){
		for(int i = 0; i < n; i++){
			for(int j = 0; j + 1 < m; j++){
				int mx = a[i][j + 1];
				for(int l = j + 2; l < m; l++){
					hori[i][j][l] = (min(a[i][l], a[i][j]) > mx);
					mx = max(mx, a[i][l]);
					if(mx > a[i][j]) break;
				}
			}
		}

		for(int j = 0; j < m; j++){
			for(int i = 0; i + 1 < n; i++){
				int mx = a[i + 1][j];
				for(int k = i + 2; k < n; k++){
					verti[i][j][k] = (min(a[k][j] , a[i][j]) > mx);
					mx = max(mx, a[k][j]);
					if(mx > a[i][j]) break;
				}
			}
		}
		for(int l = 3; l <= m; l++){
			for(int j = 0; j <= m - l; j++){
				for(int i = 0; i < n; i++){
					int pre = (i == 0 ? 0 : ph[i - 1][j][l]);
					ph[i][j][l] = pre + hori[i][j][j + l - 1];
				}
			}
		}
		for(int l = 3; l <= n; l++){
			for(int i = 0; i <= n - l; i++){
				for(int j = 0; j < m; j++){
					int pre = (j == 0 ? 0 : pv[i][j - 1][l]);
					pv[i][j][l] = pre + verti[i][j][i + l - 1];
				}
			}
		}

		for(int i = 0; i < n - 2; i++){
			for(int j = 0; j < m - 2; j++){
				for(int k = i + 2; k < n; k++){
					for(int l = j + 2; l < m; l++){
						int d1 = -ph[i][j][l - j + 1] + ph[k - 1][j][l - j + 1];

						int d2 = -pv[i][j][k - i + 1] + pv[i][l - 1][k - i + 1];

						if(d1 == k - i - 1 && d2 == l - j - 1) 
							ans++;
					}
				}
			}
		}

		return ans;
	}else if(n <= 3){
		if(n <= 2) return 0;
		ll ans = 0;
		vector<pair<int, int>> ara;
		int lastl = 0;
		for(int i = 1; i < m - 1; i++){
			if(min(a[0][i], a[2][i]) <= a[1][i]){
				if(lastl != i - 1);
					ara.push_back({lastl, i});
				lastl = i;
			}
		}
		if(lastl != m - 2) ara.push_back({lastl, m - 1});

		for(auto u: ara){
			int l = u.first, r = u.second;
			stack<int> st;
			for(int j = r; j >= l; j--){
				while(!st.empty() && a[1][st.top()] <= a[1][j]) 
					st.pop();
				if(st.empty()){
					nx[j] = r + 1;
				}else{
					nx[j] = st.top();
				}
				st.push(j);
			}

			for(int j = l; j < r - 1; j++){
				int mx = a[1][j + 1];
				int rr = nx[j + 1];
				//cerr<<j<<" "<<r<<"\n";
				//cerr<<a[1][j + 1]<<" "<<a[1][j]<<" "<<a[1][rr]<<endl;
				while(rr <= r){
					if(mx >= min(a[1][j], a[1][rr]))
						break;
					ans++;
					mx = max(mx, a[1][rr]);
					rr = nx[rr];
					//cerr<<rr<<" ";
				}
			}
		}
		return ans;
	}else{
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(i == 0 && j == 0) pre[i][j] = a[i][j];
				else if(i == 0) pre[i][j] = pre[i][j - 1] + a[i][j];
				else if(j == 0) pre[i][j] = pre[i - 1][j] + a[i][j];
				else pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + a[i][j];
			}
		}

		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(visited[i][j] || a[i][j] == 1){
					continue;
				}
				mnx[cc] = mxx[cc] = i;
				mny[cc] = mxy[cc] = j;
				dfs(i, j, a);
				int say = gtpre(mnx[cc], mny[cc], mxx[cc], mxy[cc]);
				if(say == 0 && mnx[cc] != 0 && mny[cc] != 0 && mxx[cc] != n - 1 && mxy[cc] != m - 1)
					ans++;
				cc++;
			}
		}
		return ans;
	}

}

Compilation message (stderr)

rect.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&)':
rect.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
      |              ~~^~~~~~~~~~~~
rect.cpp:15:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(i < 0 || i >= vc.size() || j < 0 || j >= vc[0].size() || vc[i][j] == 1){
      |                                         ~~^~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:109:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  109 |     if(lastl != i - 1);
      |     ^~
rect.cpp:110:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  110 |      ara.push_back({lastl, i});
      |      ^~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28