Submission #221462

#	Time	Username	Problem	Language	Result	Execution time	Memory
221462		oolimry	Rectangles (IOI19_rect)	C++14	72 / 100	5121 ms	833864 KiB

rect

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
typedef pair<int,int> ii;

int Left[2505][2505]; ///Left[r][c]: Left boundary from (r,c) provided (r,c) < (Left[r][c],c)
int Right[2505][2505]; ///Right[r][c]: Right boundary from (r,c) provided (r,c) < (Right[r][c],c)
vector<int> Up[2505][2505]; ///Up[r][c]: All upper boundary from (r,c);

vector<int> LeftRight[2505][2505]; ///LeftRight[L][R]: rows that [L,R] form a good pair
vector<int> UpDown[2505][2505]; ///Updown[T][D]: columns that [T,D] form a good pair

inline int verify(int T, int B, int L, int R){ ///check if the rectangle enclosed by T, B, L, R is good (T, B, L, R are excluded)
	int ans = 1;
	
	///number of rows between T and B (both exclusive) that form good pairs (L,R)
	if(lower_bound(all(LeftRight[L][R]), B) - upper_bound(all(LeftRight[L][R]), T) != (B - T - 1)) ans = 0;
	
	///number of cols between L and R (both exclusive) that form good pairs (T,B)
	if(lower_bound(all(UpDown[T][B]), R) - upper_bound(all(UpDown[T][B]), L) != (R - L - 1)) ans = 0;
	
	return ans;
}

long long count_rectangles(vector<vector<int> > arr) {
	int rows = arr.size();
	int cols = arr[0].size();
	
	for(int r = 0;r < rows;r++){
		for(int c = 0;c < cols;c++){
			Left[r][c] = -1;
			Right[r][c] = -1;
		}
	}
	
	for(int r = 0;r < rows;r++){
		vector<ii> s; s.push_back(ii(1e9,-1));
		//cout << r << ": \n";
		for(int i = 0;i < cols;i++){
			while(true){
				ii back = s.back();
				if(back.second != -1 && back.second != i - 1){
					//cout << s.back().second << " " << i << " " << "\n";
					int L = s.back().second;
					int R = i;
					LeftRight[L][R].push_back(r);
					
					if(arr[r][L] > arr[r][R]) Left[r][R] = L;
					else Right[r][L] = R;
				}
				if(s.back().first >= arr[r][i]){
					if(s.back().first == arr[r][i]) s.pop_back();
					break;
				}
				s.pop_back();
			}
			s.push_back(ii(arr[r][i],i));
		}
	}
	
	for(int c = 0;c < cols;c++){
		vector<ii> s; s.push_back(ii(1e9,-1));
		//cout << c << ": \n";
		for(int i = 0;i < rows;i++){
			while(true){
				ii back = s.back();
				if(back.second != -1 && back.second != i - 1){
					//cout << s.back().second << " " << i << " " << "\n";
					int T = s.back().second;
					int B = i;
					
					UpDown[T][B].push_back(c);
					
					Up[B][c].push_back(T);
					//cout << B << " " << c << " " << T << "\n";
				}
				if(s.back().first >= arr[i][c]){
					if(s.back().first == arr[i][c]) s.pop_back();
					break;
				}
				s.pop_back();
			}
			s.push_back(ii(arr[i][c],i));
		}
	}
	
	int ans = 0;
	for(int r = 1;r < rows - 1;r++){
		for(int c = 1;c < cols;c++){
			
			if(Right[r][c-1] != -1){
				int B = r + 1;
				int L = c - 1;
				int R = Right[r][L];
				for(int T : Up[B][c]){
					//cout << T << " " << B << " " << L << " " << R << " ";
					//cout << verify(T,B,L,R) << "\n";
					ans += verify(T,B,L,R);
				}
			}
			
			if(Left[r][c+1] != -1){
				//cout << r << " " << c << " " << "BR\n";
				int B = r + 1;
				int R = c + 1;
				int L = Left[r][R];
				for(int T : Up[B][c]){
					//cout << T << " " << B << " " << L << " " << R << " ";
					//cout << verify(T,B,L,R) << "\n";
					ans += verify(T,B,L,R);
				}
			}
			
		}
	}
	
	return ans;
}

• 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: 0 / 28