Submission #422827

#	Time	Username	Problem	Language	Result	Execution time	Memory
422827		donentseto	Rectangles (IOI19_rect)	C++14	0 / 100	1214 ms	703332 KiB

rect

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2505;
int n, m;
vector <int> rows [maxn][maxn], cols [maxn][maxn];
vector <pair <int, int> > rows1 [maxn][maxn], cols1 [maxn][maxn];

int fenwick [maxn];
void upd (int x, int val){
	while (x <= n){
		fenwick [x] += val;
		x += x & -x;
	}
}
int query (int x){
	int ans = 0;
	while (x > 0){
		ans += fenwick [x];
		x -= x & -x;
	}
	return ans;
}

long long count_rectangles (vector <vector <int> > a){
	
	n = a.size ();
	m = a [0].size ();
	if (n < 3 || m < 3) return 0;
	long long ans = 0;

	for (int i = n - 2; i > 0; i --){
		stack <int> s;
		s.push (0);
		for (int j = 1; j < m; j ++){
			while (!s.empty ()){
				rows [s.top () + 1][j - 1].push_back (i);
				if (a [i][s.top ()] < a [i][j]) s.pop ();
				else{
					if (a [i][s.top ()] == a [i][j]) s.pop ();
					break;
				}
			}
			s.push (j);
		}
	}
	for (int i = m - 2; i > 0; i --){
		stack <int> s;
		s.push (0);
		for (int j = 1; j < n; j ++){
			while (!s.empty ()){
				cols [s.top () + 1][j - 1].push_back (i);
				if (a [s.top ()][i] < a [j][i]) s.pop ();
				else{
					if (a [s.top ()][i] == a [j][i]) s.pop ();
					break;
				}
			}
			s.push (j);
		}
	}

	for (int i = 1; i < m - 1; i ++){
		for (int j = i; j < m - 1; j ++){
			int sz = rows [i][j].size ();
			if (sz == 0) continue;
			int last = rows [i][j][0];
			cols1 [rows [i][j][0]][i].push_back ({j, last});
			for (int x = 1; x < sz; x ++){
				if (rows [i][j][x] > rows [i][j][x - 1] + 1) last = rows [i][j][x];
				cols1 [rows [i][j][x]][i].push_back ({j, last});
			}
		}
	}
	for (int i = 1; i < n - 1; i ++){
		for (int j = i; j < n - 1; j ++){
			int sz = cols [i][j].size ();
			if (sz == 0) continue;
			int last = cols [i][j][0];
			rows1 [i][cols [i][j][0]].push_back ({last, j});
			for (int x = 1; x < sz; x ++){
				if (cols [i][j][x] > cols [i][j][x - 1] + 1) last = cols [i][j][x];
				rows1 [i][cols [i][j][x]].push_back ({last, j});
			}
		}
	}

	for (int i = 1; i < n - 1; i ++){
		for (int j = 1; j < m - 1; j ++){
			int sz_r = rows1 [i][j].size (), sz_c = cols1 [i][j].size ();
			sort (rows1 [i][j].begin (), rows1 [i][j].end ());
			int r = sz_r - 1;
			for (int c = sz_c - 1; c >= 0; c --){
				while (r >= 0 && rows1 [i][j][r].first >= cols1 [i][j][c].first){
					upd (rows1 [i][j][r].second, 1);
					r --;
				}
				ans += query (cols1 [i][j][c].second);
			}
			while (r < sz_r - 1){
				r ++;
				upd (rows1 [i][j][r].second, -1);
			}
		}
	}
	
	return ans;

}

//int main (){

	//cout << count_rectangles ({
			//{4, 8, 7, 5, 6},
			//{7, 4, 10, 3, 5},
			//{9, 7, 20, 14, 2},
			//{9, 14, 7, 3, 6},
			//{5, 7, 5, 2, 7},
			//{4, 5, 13, 5, 6}
			//}) << '\n';

//}

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