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 <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
int up[2505][2505];
int down[2505][2505];
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
i64 ans = 0;
for (int x = 0; x < n; x++)
{
for (int y = 0; y < m; y++)
{
int yu = y - 1;
int yd = y + 1;
while (yd < m && a[x][yd] < a[x][y])
yd++;
while (yu >= 0 && a[x][yu] < a[x][y])
yu--;
down[x][y] = yd - y - 1;
up[x][y] = y - yu - 1;
}
}
for (int l = 0; l < n - 2; l++)
{
vector<int> dnow(m, 987654321);
vector<int> unow(m, 987654321);
vector<int> maxv(m, 0); // 좌우에서 y별 최댓값값
for (int r = l + 2; r < n; r++)
{
vector<int> newup(m + 1, 0);
vector<int> newdown(m + 1, 0);
vector<int> delup(m + 1, 0);
vector<int> deldown(m + 1, 0);
vector<int> lrup(m + 1, 0);
vector<int> lrdown(m + 1, 0);
vector<bool> lr(m, 0); // l - r은 가능한지
for (int y = 0; y < m; y++)
{
dnow[y] = min(dnow[y], down[r - 1][y]);
unow[y] = min(unow[y], up[r - 1][y]);
maxv[y] = max(maxv[y], a[r - 1][y]);
lr[y] = maxv[y] < a[l][y] && maxv[y] < a[r][y];
}
int lru = 0, lrd = 0;
vector<int> dval(m + 1, 0);
vector<int> uval(m + 1, 0);
for (int y = 0; y < m; y++)
{
uval[y] = min(unow[y], lru);
if (lr[y])
lru++;
else
lru = 0;
}
for (int y = m - 1; y >= 0; y--)
{
dval[y] = min(dnow[y], lrd);
if (lr[y])
lrd++;
else
lrd = 0;
}
for (int y = 0; y < m; y++)
{
if (uval[y] >= 1)
{
newup[y - uval[y]]++;
delup[y]++;
}
if (dval[y] >= 1)
{
newdown[y + 1]++;
deldown[y + dval[y] + 1]++;
}
}
int tu = 0, td = 0;
for (int y = 0; y < m; y++)
{
tu -= delup[y];
td -= deldown[y];
tu += newup[y];
td += newdown[y];
if (newdown[y] > 0)
ans += tu;
}
}
}
return ans;
}
# | 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... |