Submission #423026

#	Time	Username	Problem	Language	Result	Execution time	Memory
423026		donentseto	Rectangles (IOI19_rect)	C++14	100 / 100	3518 ms	779460 KiB

rect

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

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

bool comp (pair <int, int> p1, pair <int, int> p2){
	return p1.second < p2.second || p1.second == p2.second && p1.first < p2.first;
}

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;

	stack <short> s;
	for (int i = n - 2; i > 0; i --){
		s.push (0);
		for (int j = 1; j < m; j ++){
			while (!s.empty ()){
				if (s.top () != j - 1) cols1 [i][s.top () + 1].push_back ({j - 1, 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);
		}
		while (!s.empty()) s.pop ();
	}
	for (int i = m - 2; i > 0; i --){
		s.push (0);
		for (int j = 1; j < n; j ++){
			while (!s.empty ()){
				if (s.top () != j - 1) rows1 [s.top () + 1][i].push_back ({j - 1, 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);
		}
		while (!s.empty()) s.pop ();
	}

	vector <pair <short, short> > :: iterator it;
	int sz_r, sz_c, r, c, x;
	for (int i = n - 2; i > 0; i --){
		for (int j = m - 2; j > 0; j --){
			sz_r = rows1 [i][j].size ();
			sz_c = cols1 [i][j].size ();
			for (r = 0; r < sz_r; r ++){
				it = lower_bound (rows1 [i][j + 1].begin (), rows1 [i][j + 1].end (), make_pair (rows1 [i][j][r].first, (short) 0));
				if (it != rows1 [i][j + 1].end () && it->first == rows1 [i][j][r].first) rows1 [i][j][r].second = it->second;
			}
			for (c = 0; c < sz_c; c ++){
				it = lower_bound (cols1 [i + 1][j].begin (), cols1 [i + 1][j].end (), make_pair (cols1 [i][j][c].first, (short) 0));
				if (it != cols1 [i + 1][j].end () && it->first == cols1 [i][j][c].first) cols1 [i][j][c].second = it->second;
			}
		}
	}

	for (int i = 1; i < n - 1; i ++){
		for (int j = 1; j < m - 1; j ++){
			sz_r = rows1 [i][j].size (), sz_c = cols1 [i][j].size ();
			sort (rows1 [i][j].begin (), rows1 [i][j].end (), comp);
			r = sz_r - 1;
			for (c = sz_c - 1; c >= 0; c --){
				while (r >= 0 && rows1 [i][j][r].second >= cols1 [i][j][c].first){
					x = rows1 [i][j][r].first;
					while (x <= n){
						fenwick [x] ++;
						x += x & -x;
					}
					r --;
				}
				x = cols1 [i][j][c].second;
				while (x > 0){
					ans += fenwick [x];
					x -= x & -x;
				}
			}
			while (r < sz_r - 1){
				r ++;
				x = rows1 [i][j][r].first;
				while (x <= n){
					fenwick [x] --;
					x += x & -x;
				}
			}
		}
	}
	
	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 ++){
				//rows1 [i][j].clear ();
				//cols1 [i][j].clear ();
			//}
		//}
	//}

//}

Compilation message (stderr)

rect.cpp: In function 'bool comp(std::pair<int, int>, std::pair<int, int>)':
rect.cpp:10:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   10 |  return p1.second < p2.second || p1.second == p2.second && p1.first < p2.first;
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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