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"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int S = 2500 * 2500 + 5, N = 2505;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
vector<pii> qs[N][N];
bool bad[N][N];
vector<pair<pii, pii>> trims;
vector<vector<int>> mx;
vector<vector<int>> lf, rt, bt, tp;
int n, m;
static void scanner() {
lf = vector<vector<int>>(n, vector<int>(m));
rt = vector<vector<int>>(n, vector<int>(m));
tp = vector<vector<int>>(n, vector<int>(m));
bt = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
vector<int> stk;
for (int j = 0; j < m; ++j) { // left
while (!stk.empty() && mx[i][stk.back()] <= mx[i][j])
stk.pop_back();
lf[i][j] = stk.empty() ? -1 : stk.back();
stk.push_back(j); }
stk.clear();
for (int j = m - 1; j > 0; --j) { // right
while (!stk.empty() && mx[i][stk.back()] <= mx[i][j])
stk.pop_back();
rt[i][j] = stk.empty() ? -1 : stk.back();
stk.push_back(j); } }
for (int j = 0; j < m; ++j) {
vector<int> stk;
for (int i = 0; i < n - 1; ++i) { // top
while (!stk.empty() && mx[stk.back()][j] <= mx[i][j])
stk.pop_back();
tp[i][j] = stk.empty() ? -1 : stk.back();
stk.push_back(i); }
stk.clear();
for (int i = n - 1; i > 0; --i) { // bottom
while (!stk.empty() && mx[stk.back()][j] <= mx[i][j])
stk.pop_back();
bt[i][j] = stk.empty() ? -1 : stk.back();
stk.push_back(i); } } }
static void run_vertical() {
vector<int> h_stk, stk[N];
int h[N];
for (int i = 1; i < n - 1; ++i)
for (int j = 1; j < m - 1; ++j) {
if (rt[i][j] == -1 || lf[i][j] == -1 || tp[i][j] == -1 || bt[i][j] == -1 || bad[i][j]) {
bad[i][j] = true; }
else {
qs[tp[i][j]][rt[i][j] - 1].emplace_back(i, j);
qs[bt[i][j]][rt[i][j] - 1].emplace_back(-i, -j); } }
// bottom radiates up
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
while (!stk[j].empty() && mx[stk[j].back()][j] < mx[i][j])
stk[j].pop_back();
h[j] = stk[j].empty() ? 0 : stk[j].back();
stk[j].push_back(i); }
h_stk.clear();
for (int j = 0; j < m; ++j) {
while (!h_stk.empty() && h[h_stk.back()] > h[j])
h_stk.pop_back();
h_stk.push_back(j);
for (auto q: qs[i][j]) if (q.x < 0) { // actually query handling
int pos = -1, bnd = lf[-q.x][-q.y];
for (int msk = 1 << 11; msk > 0; msk/= 2)
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
pos+= msk;
pos+= 1;
if (h[h_stk[pos]] > tp[-q.x][-q.y] && !bad[-q.x][-q.y])
bad[-q.x][-q.y] = true; } } }
for (int i = 0; i < N; ++i)
stk[i].clear();
// top radiates down
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < m; ++j) {
while (!stk[j].empty() && mx[stk[j].back()][j] < mx[i][j])
stk[j].pop_back();
h[j] = stk[j].empty() ? 1e9 : stk[j].back();
stk[j].push_back(i); }
h_stk.clear();
for (int j = 0; j < m; ++j) {
while (!h_stk.empty() && h[h_stk.back()] < h[j])
h_stk.pop_back();
h_stk.push_back(j);
for (auto q: qs[i][j]) if (q.x > 0) { // actually query handling
int pos = -1, bnd = lf[q.x][q.y];
for (int msk = 1 << 11; msk > 0; msk/= 2)
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
pos+= msk;
pos+= 1;
if (h[h_stk[pos]] < bt[q.x][q.y] && !bad[q.x][q.y])
bad[q.x][q.y] = true; } } } }
static void run_horizontal() {
vector<int> h_stk, stk[N];
int h[N];
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
qs[i][j].clear();
for (int i = 1; i < n - 1; ++i)
for (int j = 1; j < m - 1; ++j) {
if (rt[i][j] == -1 || lf[i][j] == -1 || tp[i][j] == -1 || bt[i][j] == -1 || bad[i][j]) {
bad[i][j] = true; }
else {
qs[tp[i][j] + 1][lf[i][j]].emplace_back(i, j);
qs[tp[i][j] + 1][rt[i][j]].emplace_back(-i, -j); } }
// right radiates left
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
while (!stk[i].empty() && mx[i][stk[i].back()] < mx[i][j])
stk[i].pop_back();
h[i] = stk[i].empty() ? 0 : stk[i].back();
stk[i].push_back(j); }
h_stk.clear();
for (int i = 0; i < n; ++i) {
while (!h_stk.empty() && h[h_stk.back()] > h[i])
h_stk.pop_back();
h_stk.push_back(i);
for (auto q: qs[i][j]) if (q.x < 0) { // actually query handling
int pos = -1, bnd = lf[-q.x][-q.y];
for (int msk = 1 << 11; msk > 0; msk/= 2)
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
pos+= msk;
pos+= 1;
if (h[h_stk[pos]] > lf[-q.x][-q.y] && !bad[-q.x][-q.y])
bad[-q.x][-q.y] = true; } } }
for (int i = 0; i < N; ++i)
stk[i].clear();
// left radiates right
for (int j = m - 1; j >= 0; --j) {
for (int i = 0; i < n; ++i) {
while (!stk[i].empty() && mx[i][stk[i].back()] < mx[i][j])
stk[i].pop_back();
h[i] = stk[i].empty() ? 1e9 : stk[i].back();
stk[i].push_back(j); }
h_stk.clear();
for (int i = 0; i < n; ++i) {
while (!h_stk.empty() && h[h_stk.back()] < h[i])
h_stk.pop_back();
h_stk.push_back(i);
for (auto q: qs[i][j]) if (q.x > 0) { // actually query handling
int pos = -1, bnd = rt[q.x][q.y];
for (int msk = 1 << 11; msk > 0; msk/= 2)
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
pos+= msk;
pos+= 1;
if (h[h_stk[pos]] < rt[q.x][q.y] && !bad[q.x][q.y])
bad[q.x][q.y] = true; } } } }
static void pulatronizate() {
for (int i = 1; i + 1 < n; ++i)
for (int j = 1; j + 1 < m; ++j) if (!bad[i][j]) {
trims.emplace_back(pii(lf[i][j], tp[i][j]), pii(rt[i][j], bt[i][j])); } }
i64 count_rectangles(vector<vector<int>> _mx) {
n = _mx.size(), m = _mx[0].size();
swap(mx, _mx);
scanner();
run_vertical();
run_horizontal();
pulatronizate();
sort(begin(trims), end(trims));
trims.erase(unique(begin(trims), end(trims)), end(trims));
return trims.size(); }
Compilation message (stderr)
rect.cpp: In function 'void run_vertical()':
rect.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:118:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp: In function 'void run_horizontal()':
rect.cpp:157:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:183:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
~~~~~~~~~~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |