| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 579423 | djs100201 | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "rect.h"
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using ll = long long;
using namespace std;
const int n_ = 505;
using P = pair<int, int>;
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
int R[n_][n_], U[n_][n_], D[n_][n_], L[n_][n_];
vector<int>row[n_][n_], idx[n_][n_];
ll tree_[n_];
ll f(ll l, ll r) {
r++;
ll ret = 0;
for (; l; l -= (l & -l))ret -= tree_[l];
for (; r; r -= (r & -r))ret += tree_[r];
return ret;
}
void update(ll i, ll val) {
i++;
for (; i <= n; i += i & -i)tree_[i] += val;
}
long long count_rectangles(std::vector<std::vector<int> > arr) {
ll ret = 0;
n = arr.size();
m = arr[0].size();
for (int i = 0; i < n; i++) {
stack<P>A, B;
A.push({ arr[i][0],0 });
B.push({ arr[i][m - 1],m - 1 });
for (int j = 1; j < m; j++) {
while (A.size() && A.top().first <= arr[i][j])A.pop();
if (A.empty())L[i][j] = -1;
else L[i][j] = A.top().second;
A.push({ arr[i][j],j });
while (B.size() && B.top().first <= arr[i][m - 1 - j])B.pop();
if (B.empty())R[i][m - 1 - j] = -1;
else R[i][m - 1 - j] = B.top().second;
B.push({ arr[i][m - 1 - j],m - 1 - j });
}
}
for (int i = 0; i < m; i++) {
stack<P>A, B;
A.push({ arr[0][i],0 });
B.push({ arr[n - 1][i],n - 1 });
for (int j = 1; j < n; j++) {
while (A.size() && A.top().first <= arr[j][i])A.pop();
if (A.empty())U[j][i] = -1;
else U[j][i] = A.top().second;
A.push({ arr[j][i],j });
while (B.size() && B.top().first <= arr[n - 1 - j][i])B.pop();
if (B.empty())D[n - 1 - j][i] = -1;
else D[n - 1 - j][i] = B.top().second;
B.push({ arr[n - 1 - j][i],n - 1 - j });
}
}
vector<vector<int>>query;
for (int j = 1; j + 1 < m; j++)
for (int i = 1; i + 1 < n; i++) {
if (D[i][j] != -1 && U[i][j] != -1) {
if (row[U[i][j]][D[i][j]].size() && row[U[i][j]][D[i][j]].back() == j)continue;
row[U[i][j]][D[i][j]].push_back(j);
if (L[i][j] != -1 && R[i][j] != -1) {
query.push_back({ L[i][j],R[i][j],U[i][j],D[i][j] });
}
}
}
sort(all(query));
query.erase(unique(query.begin(), query.end()), query.end());
int cnt = 0;
for (auto nxt : query) {
idx[nxt[2]][nxt[3]].push_back(cnt);
cnt++;
}
assert(cnt <= n * m);
vector<int>now(cnt + 1);
for (int i = 0; i < n; i++)
for (int j = i + 2; j < n; j++) {
for (auto nxt : row[i][j])update(nxt, 1);
for (auto nxt : idx[i][j]) {
ll l = query[nxt][0], r = query[nxt][1];
int len = f(l + 1, r - 1);
if (len == r - l - 1)now[nxt]++;
}
for (auto nxt : row[i][j])update(nxt, -1);
row[i][j].clear();
idx[i][j].clear();
}
cnt = 0;
for (auto nxt : query) {
idx[nxt[0]][nxt[1]].push_back(cnt);
cnt++;
}
for (int i = 1; i + 1 < n; i++)
for (int j = 1; j + 1 < m; j++) {
if (L[i][j] != -1 && R[i][j] != -1) {
if (row[L[i][j]][R[i][j]].size() && row[L[i][j]][R[i][j]].back() == i)continue;
row[L[i][j]][R[i][j]].push_back(i);
}
}
for (int i = 0; i < m; i++)
for (int j = i + 2; j < m; j++) {
for (auto nxt : row[i][j])update(nxt, 1);
for (auto nxt : idx[i][j]) {
if (now[nxt] == 0)continue;
ll l = query[nxt][2], r = query[nxt][3];
int len = f(l + 1, r - 1);
if (len == r - l - 1)ret++;
}
for (auto nxt : row[i][j])update(nxt, -1);
}
return ret;
}
int main() {
cin >> n >> m;
vector<vector<int>>arr(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a;
arr[i].push_back(a);
}
}
cout << count_rectangles(arr) << endl;
}