| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 584572 | 8e7 | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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])) {
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 {
for (auto x:p) good[x.ff][x.ss] &= row[x.ff][x.ss];
p.clear();
for (auto x:q) {
if (good[x.ff][x.ss]) p.push_back(x);
row[x.ff][x.ss] = 0;
}
}
//for (auto x:p) debug(x.ff, x.ss);
//debug();
}
for (auto x:p) good[x.ff][x.ss] = 0;
}
return ret;
}