Submission #402092

#	Time	Username	Problem	Language	Result	Execution time	Memory
402092		b00n0rp	Rectangles (IOI19_rect)	C++17	72 / 100	3105 ms	1048580 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
 
const int MX = 2505;
 
ll ans = 0;
int n,m; 
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
vector<pii> row_seg[MX][MX],col_seg[MX][MX];

unordered_set<int> rects[MX][MX];

void check_rectangle(int x1,int y1,int x2,int y2){
	if(rects[x1][y1].find(x2*MX+y2) != rects[x1][y1].end()) return;
	
	auto it = lower_bound(all(row_seg[y1-1][y2+1]),make_pair(x1,MX));
	if(it == row_seg[y1-1][y2+1].begin()) return;
	it--;
	if((*it).S < x2) return;

	it = lower_bound(all(col_seg[x1-1][x2+1]),make_pair(y1,MX));
	if(it == col_seg[x1-1][x2+1].begin()) return;
	it--;
	if((*it).S < y2) return;

	rects[x1][y1].insert(x2*MX+y2);
	ans++;
}
 
ll count_rectangles(vector<vi> a) {
	n = a.size();
	m = a[0].size();
	if(n <= 2 or m <= 2) return 0;
	REP(i,n){
		stack<int> st;
		REP(j,m){
			gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
		}
		REP(j,m){
			while(st.size() and a[i][st.top()] <= a[i][j]){
				gr[i][st.top()] = j;
				st.pop();
			}
			st.push(j);
		}
		while(!st.empty()) st.pop();
		FORD(j,m-1,0){
			while(st.size() and a[i][st.top()] <= a[i][j]){
				gl[i][st.top()] = j;
				st.pop();
			}
			st.push(j);
		}
		REP(j,m){
			if(gr[i][j] != -1 and gr[i][j] != j+1){
				if(row_seg[j][gr[i][j]].empty() or i-1 > row_seg[j][gr[i][j]].back().S){
					row_seg[j][gr[i][j]].pb({i,i});
				}
				else row_seg[j][gr[i][j]].back().S++;
			}
			if(gl[i][j] != -1 and gl[i][j] != j-1 and gr[i][gl[i][j]] != j){
				if(row_seg[gl[i][j]][j].empty() or i-1 > row_seg[gl[i][j]][j].back().S){
					row_seg[gl[i][j]][j].pb({i,i});
				}
				else row_seg[gl[i][j]][j].back().S++;
			}
		}
	}
	REP(j,m){
		stack<int> st;
		REP(i,n){
			while(st.size() and a[st.top()][j] <= a[i][j]){
				gd[st.top()][j] = i;
				st.pop();
			}
			st.push(i);
		}
		while(!st.empty()) st.pop();
		FORD(i,n-1,0){
			while(st.size() and a[st.top()][j] <= a[i][j]){
				gu[st.top()][j] = i;
				st.pop();
			}
			st.push(i);
		}
		REP(i,n){
			if(gd[i][j] != -1 and gd[i][j] != i+1){
				if(col_seg[i][gd[i][j]].empty() or j-1 > col_seg[i][gd[i][j]].back().S){
					col_seg[i][gd[i][j]].pb({j,j});
				}
				else col_seg[i][gd[i][j]].back().S++;
			}
			if(gu[i][j] != -1 and gu[i][j] != i-1 and gd[gu[i][j]][j] != i){
				if(col_seg[gu[i][j]][i].empty() or j-1 > col_seg[gu[i][j]][i].back().S){
					col_seg[gu[i][j]][i].pb({j,j});
				}
				else col_seg[gu[i][j]][i].back().S++;
			}
		}
	}
	FOR(i,1,n-1){
		FOR(j,1,m-1){
			// topleft
			if(gr[i][j-1] != -1 and gd[i-1][j] != -1){
				check_rectangle(i,j,gd[i-1][j]-1,gr[i][j-1]-1);
			}
			// topright
			if(gl[i][j+1] != -1 and gd[i-1][j] != -1){
				check_rectangle(i,gl[i][j+1]+1,gd[i-1][j]-1,j);
			}
			// bottomleft
			if(gr[i][j-1] != -1 and gu[i+1][j] != -1){
				check_rectangle(gu[i+1][j]+1,j,i,gr[i][j-1]-1);
			}
			// bottomright
			if(gl[i][j+1] != -1 and gu[i+1][j] != -1){
				check_rectangle(gu[i+1][j]+1,gl[i][j+1]+1,i,j);
			}
			// clockwise
			if(gr[i][j-1] != -1 and gd[i-1][gr[i][j-1]-1] != -1){
				check_rectangle(i,j,gd[i-1][gr[i][j-1]-1]-1,gr[i][j-1]-1);
			}
			// anti-clockwise
			if(gl[i][j+1] != -1 and gd[i-1][gl[i][j+1]+1] != -1){
				check_rectangle(i,gl[i][j+1]+1,gd[i-1][gl[i][j+1]+1]-1,j);
			}
		}
	}
	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