Submission #422891

#	Time	Username	Problem	Language	Result	Execution time	Memory
422891		donentseto	Rectangles (IOI19_rect)	C++14	72 / 100	3051 ms	1048580 KiB

rect

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

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

short 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 ()){
				if (s.top () != j - 1) 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 ()){
				if (s.top () != j - 1) 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;

}

//long long bruteforce (vector <vector <int> > a){

	//n = a.size ();
	//m = a [0].size ();
	//if (n < 3 || m < 3) return 0;
	//long long ans = 0;
	
	//for (int u = 1; u < n - 1; u ++){
		//for (int d = u; d < n - 1; d ++){
			//for (int l = 1; l < m - 1; l ++){
				//for (int r = l; r < m - 1; r ++){
					//bool flag = 1;
					//for (int i = u; i <= d; i ++){
						//for (int j = l; j <= r; j ++){
							//if (a [i][j] >= a [u - 1][j] || a [i][j] >= a [d + 1][j] || a [i][j] >= a [i][l - 1] || a [i][j] >= a [i][r + 1]){
								//flag = 0;
								//break;
							//}
						//}
						//if (!flag) break;
					//}
					//ans += flag;
				//}
			//}
		//}
	//}

	//return ans;

//}

//mt19937 mt (5172893);

//int main (){

	//while (1){
		//n = mt () % 5 + 1;
		//m = mt () % 5 + 1;
		//vector <vector <int> > a (n);
		//for (int i = 0; i < n; i ++){
			//for (int j = 0; j < m; j ++){
				//a [i].push_back (mt () % 10);
			//}
		//}
		//long long ans1 = count_rectangles (a);
		//long long ans2 = bruteforce (a);
		//if (ans1 != ans2){
			//cout << "damn\n";
			//cout << ans1 << ' ' << ans2 << '\n';
			//cout << n << ' ' << m << '\n';
			//for (auto v : a){
				//for (auto i : v) cout << i << ' ';
				//cout << '\n';
			//}
			//return 0;
		//}
		//cout << "ok\n";
		//for (int i = 0; i <= 30; i ++){
			//for (int j = 0; j <= 30; j ++){
				//rows [i][j].clear ();
				//cols [i][j].clear ();
				//rows1 [i][j].clear ();
				//cols1 [i][j].clear ();
			//}
		//}
	//}

//}

• 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