Submission #1281673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281673		nicolo_010	Rectangles (IOI19_rect)	C++20	10 / 100	5098 ms	68252 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m;

bool valid(int x, int y) {
	if (x >= 0 && x<n && y >= 0 && y < m) return true;
	else return false;
}

struct SegTree {
	vector<int> tree;
	SegTree(int n) {
		tree.assign(4*n, 0);
	}
	void query(int p, int l, int r, int i, int x) {
		if (l > i || r < i) return;
		if (l==r && l==i) {
			tree[p] = x;
		}
		else {
			int m = (l+r)/2;
			query(2*p, l, m, i, x);
			query(2*p+1, m+1, r, i, x);
			tree[p] = max(tree[2*p], tree[2*p+1]);
		}
	}
	int rmq(int p, int l, int r, int i, int j) {
		if (l > j || r < i) return 0;
		if (i<=l && r <= j) {
			return tree[p];
		}
		int m = (l+r)/2;
		int i1 = rmq(2*p, l, m, i, j);
		int i2 = rmq(2*p+1, m+1, r, i, j);
		return max(i1, i2);
	}
};

ll count_rectangles(vector<vector<int>> a) {
	n = a.size();
	if (n <= 2) return 0;
	m = a[0].size();
	vector<int> dx = {1, 0, -1, 0};
	vector<int> dy = {0, 1, 0, -1};
	vector<vector<bool>> vis(n, vector<bool>(m, false));
	/*vector<vector<int>> rows(n, vector<int>(m, 0));
	for (int i=0; i<n; i++) {
		rows[i][0] = a[i][0];
		for (int j=1; j<m; j++) {
			rows[i][j] = rows[i][j-1] + a[i][j];
		}
	}
	vector<vector<int>> col(m, vector<int>(n, 0));
	for (int i=0; i<m; i++) {
		col[i][0] = a[0][i];
		for (int j=1; j<n; j++) {
			col[i][j] = a[j][i] + col[i][j-1];
		}
	}*/
	vector<int> pref(m, 0);
	vector<int> b(m);
	for (int i=0; i<m; i++) {
		b[i] = (a[1][i] < a[0][i] && a[1][i] < a[2][i]);
	}
	ll cnt=0;
	vector<SegTree> st;
	for (int i=0; i<m; i++) {
		st.emplace_back(n);
	}
	for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
			st[i].query(1, 0, n-1, j, a[j][i]);
		}
	}
	for (int i1=1; i1<n-1; i1++) {
		for (int j1=1; j1<m-1; j1++) {
			vector<bool> valid(n, true);
			vector<int> rows(n, 0);
			for (int j2=j1; j2<m-1; j2++) {
				for (int i2=i1; i2<n-1; i2++) {
					rows[i2] = max(rows[i2], a[i2][j2]);
					int q = st[j2].rmq(1, 0, n-1, i1, i2);
					if (a[i1-1][j2] <= q || a[i2+1][j2] <= q) {
						valid[i2] = false;
					}
					if (rows[i2] < a[i2][j1-1] && rows[i2] < a[i2][j2+1] && valid[i2]) {
						cnt++;
					}
					else if (!(rows[i2] < a[i2][j1-1] && rows[i2] < a[i2][j2+1])) break;
				}
			}
		}
	}
	return cnt;
}

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