Submission #147148

#	Time	Username	Problem	Language	Result	Execution time	Memory
147148		Mamnoon_Siam	Rectangles (IOI19_rect)	C++17	59 / 100	3918 ms	1048580 KiB

rect

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

using ii = pair<int, int>;
using ll = long long;
const int N = 2500;
const int inf = 1e9;

int n, m;
int g[N][N];
bitset<N> ls[N][N];
int mxx[N];

long long count_rectangles(vector<vector<int> > _a) {
	n = _a.size(), m = _a[0].size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			g[i][j] = _a[i][j];
		}
	}
	for(int i = 1; i < n - 1; i++) {
		for(int j = 1; j < m - 1; j++) {
			int mx = -inf;
			for(int k = j; k > 0; k--) {
				mx = max(mx, g[i][k]);
				if(mx < g[i][j + 1]) {
					if(mx < g[i][k - 1]) {
						ls[i][j][k] = 1;
					}
				} else {
					break;
				}
			}
		}
	}
	int ans = 0;
	for(int u = 1; u < n - 1; u++) {
		for(int i = 1; i < m - 1; i++) {
			mxx[i] = -inf;
		}
		for(int v = u; v < n - 1; v++) {
			bitset<N> can;
			for(int i = 1; i < m - 1; i++) {
				mxx[i] = max(mxx[i], g[v][i]);
				if(mxx[i] < g[u - 1][i] and mxx[i] < g[v + 1][i]) {
					can[i] = 1;
				}
			}
			int now = 0;
			while(can._Find_next(now) < m - 1) {
				int l = can._Find_next(now);
				int r = l;
				while(can[r + 1]) {
					r++;
				}
				bitset<N> range;
				for(int i = l; i <= r; i++) {
					range[i] = 1;
				}
				for(int j = l; j <= r; j++) {
					bitset<N> intersection = range;
					for(int i = u; i <= v; i++) {
						intersection &= ls[i][j];
						if(intersection.count() == 0) {
							break;
						}
					}
					ans += intersection.count();
				}
				now = r;
			}
		}
		move_u : ;
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:51:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(can._Find_next(now) < m - 1) {
          ~~~~~~~~~~~~~~~~~~~~^~~~~~~
rect.cpp:74:3: warning: label 'move_u' defined but not used [-Wunused-label]
   move_u : ;
   ^~~~~~

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