Submission #584557

#	Time	Username	Problem	Language	Result	Execution time	Memory
584557		8e7	Rectangles (IOI19_rect)	C++17	10 / 100	5054 ms	29616 KiB

rect

#include "rect.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();	
	vector<vector<bool> > good(m, vector<bool>(m, 0)), row(m, vector<bool>(m, 0));
	
	ll ret = 0;
	for (int u = 1;u < n - 1;u++) {
		vector<int> ma(m, 0);
		vector<pii> p;
		for (int d = u;d < n - 1;d++) {
			int lef = 0;
			stack<int> stk;

			vector<pii> q;
			for (int i = 0;i < m;i++) {
				
				auto add = [&] (int l, int r) {
					if (l+1 < r) {
						if (l >= lef && (u == d || good[l][r])) {
							debug(u, d, l, r);
							ret++;
						}
						q.push_back({l, r});
						row[l][r] = 1;
					}
				};
				bool check = 1;
				while (stk.size() && a[d][i] >= a[d][stk.top()]) {
					int l = stk.top();
					add(l, i);	
					if (a[d][l] == a[d][i]) check = 0;
					stk.pop();
				}
				if (check && stk.size()) {
					add(stk.top(), i);
				}
				stk.push(i);

				ma[i] = max(ma[i], a[d][i]);	
				if (ma[i] >= a[u-1][i] || ma[i] >= a[d+1][i]) {
					lef = i;
				}
			}
			if (u == d) {
				for (auto x:q) good[x.ff][x.ss] = 1, row[x.ff][x.ss] = 0;
				p = q;
			} else {
				p.clear();
				for (auto x:p) {
					if (!row[x.ff][x.ss]) good[x.ff][x.ss] = 0;
				}
				for (auto x:q) {
					if (good[x.ff][x.ss]) p.push_back(x);
					row[x.ff][x.ss] = 0;
				}
			}
		}
	}
	return ret;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
rect.cpp:42:8: note: in expansion of macro 'debug'
   42 |        debug(u, d, l, r);
      |        ^~~~~

• 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