Submission #295297

#	Time	Username	Problem	Language	Result	Execution time	Memory
295297		Atill83	Rectangles (IOI19_rect)	C++14	37 / 100	1018 ms	82296 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];
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{


	}

}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:76:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   76 |     if(lastl != i - 1);
      |     ^~
rect.cpp:77:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   77 |      ara.push_back({lastl, i});
      |      ^~~
rect.cpp:118:1: warning: control reaches end of non-void function [-Wreturn-type]
  118 | }
      | ^

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