Submission #224489

#	Time	Username	Problem	Language	Result	Execution time	Memory
224489		oolimry	Rectangles (IOI19_rect)	C++14	100 / 100	4872 ms	846816 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#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)
static vector<int> Up[2505][2505]; ///Up[r][c]: All upper boundary from (r,c);

static vector<int> LeftRight[2505][2505]; ///LeftRight[L][R]: rows that [L,R] form a good pair
static 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 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;
	
	///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 = -1;
	
	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++){
		stack<ii> s; s.push(ii(1e9,-1));
		for(int i = 0;i < cols;i++){
			while(true){
				ii back = s.top();
				if(back.second != -1 && back.second != i - 1){
					int L = s.top().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.top().first >= arr[r][i]){
					if(s.top().first == arr[r][i]) s.pop();
					break;
				}
				s.pop();
			}
			s.push(ii(arr[r][i],i));
		}
	}
	
	for(int c = 0;c < cols;c++){
		stack<ii> s; s.push(ii(1e9,-1));
		for(int i = 0;i < rows;i++){
			while(true){
				ii back = s.top();
				if(back.second != -1 && back.second != i - 1){
					int T = s.top().second;
					int B = i;
					
					UpDown[T][B].push_back(c);
					Up[B][c].push_back(T);
				}
				if(s.top().first >= arr[i][c]){
					if(s.top().first == arr[i][c]) s.pop();
					break;
				}
				s.pop();
			}
			s.push(ii(arr[i][c],i));
		}
	}
	
	for(int r = 0;r < rows;r++){
		for(int c = 0;c < cols;c++){
			sort(Up[r][c].begin(),Up[r][c].end());
			//for(int x : Up[r][c]) cout << x << " ";
			//cout << "\n";
		}
	}
	
	int ans = 0;
	for(int r = 1;r < rows - 1;r++){
		for(int c = 1;c < cols - 1;c++){
			
			if(Right[r][c-1] != -1){
				int B = r + 1;
				int L = c - 1;
				int R = Right[r][L];
				for(int i = (int)Up[B][c].size() - 1;i >= 0;i--){
					int T = Up[B][c][i];
					int v = verify(T,B,L,R);
					if(v == 1) ans++;
					else if(v == -1) break;
				}
			}
			
			if(Left[r][c+1] != -1){
				int B = r + 1;
				int R = c + 1;
				int L = Left[r][R];
				for(int i = (int)Up[B][c].size() - 1;i >= 0;i--){
					int T = Up[B][c][i];
					int v = verify(T,B,L,R);
					if(v == 1) ans++;
					else if(v == -1) break;
				}
			}
			
		}
	}
	
	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: 28 / 28