Submission #361585

#	Time	Username	Problem	Language	Result	Execution time	Memory
361585		saarang123	Rectangles (IOI19_rect)	C++17	8 / 100	5055 ms	73580 KiB

rect

#include <bits/stdc++.h>
using namespace std;
const int N = 2502;

template<class T> struct Seg { // comb(ID,b) = b
	T ID = T();
    function<T(const T&,const T&)> comb;
	int n; vector<T> seg;
	void init(int _n, T base, function<T(const T&,const T&)> join) {
	    n = _n; comb = join; ID = base; seg.assign(2 * n, ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n - 1] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n-1, r += n; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
	void build(vector<T> a) {
        for(int i = 1; i <= n; i++) seg[n + i - 1] = a[i - 1];
        for(int i = n - 1; i > 0; i--) seg[i] = comb(seg[i << 1], seg[i << 1|1]);
	}
};

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	vector<Seg<int>> rows(n);
	for(int i = 0; i < n; i++) {
		rows[i].init(m, 0, [&] (int x, int y) {
			return max(x, y);
		});
	}
	vector<Seg<int>> columns(m);
	for(int i = 0; i < m; i++) {
		columns[i].init(n, 0, [&] (int x, int y) {
			return max(x, y);
		});
	}
	for(int i = 0; i < n; i++)
		rows[i].build(a[i]);
	for(int j = 0; j < m; j++)
		for(int i = 0; i < n; i++)
			columns[j].upd(i + 1, a[i][j]);
	//cout << "Done till segtree build" << endl;
	long long ans = 0;
	for(int r1 = 1; r1 < n - 1; r1++) {
		for(int c1 = 1; c1 < m - 1; c1++) {
			for(int r2 = r1; r2 < n - 1; r2++) {
				for(int c2 = c1; c2 < m - 1; c2++) {
					//if(r1 == r2 && c1 == c2) continue;
					bool flag = 1;
					for(int i = r1; i <= r2; i++)
						flag &= (rows[i].query(c1 + 1, c2 + 1) < min(a[i][c1 - 1], a[i][c2 + 1]));
					for(int i = c1; i <= c2; i++)
						flag &= (columns[i].query(r1 + 1, r2 + 1) < min(a[r1 - 1][i], a[r2 + 1][i]));
					ans += flag;
				}
			}
		}
	}
	return ans;
}

• Subtask 1: 8 / 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