| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 291793 | keko37 | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 705;
const int INF = 1000000007;
int n, m, curr, sol;
int a[MAXN][MAXN], mn[MAXN];
int lef[MAXN][MAXN], rig[MAXN][MAXN];
vector <pi> v[MAXN];
int ok[MAXN], cnt[MAXN][MAXN];
void precompute_row (int r) {
vector <int> st;
for (int c = 0; c < m; c++) {
while (!st.empty() && a[r][st.back()] < a[r][c]) st.pop_back();
lef[r][c] = (st.empty() ? -1 : st.back());
st.push_back(c);
if (lef[r][c] != -1 && lef[r][c] != c - 1) v[r].push_back({lef[r][c] + 1, c - 1});
}
st.clear();
for (int c = m - 1; c >= 0; c--) {
while (!st.empty() && a[r][st.back()] < a[r][c]) st.pop_back();
rig[r][c] = (st.empty() ? -1 : st.back());
st.push_back(c);
if (rig[r][c] != -1 && rig[r][c] != c + 1) v[r].push_back({c + 1, rig[r][c] - 1});
}
sort(v[r].begin(), v[r].end());
v[r].erase(unique(v[r].begin(), v[r].end()), v[r].end());
}
inline sum (int a, int b) {
if (a == 0) return ok[b];
return ok[b] - ok[a - 1];
}
void add_row (int r) {
for (auto par : v[r]) {
int a = par.first, b = par.second;
cnt[a][b]++;
if (cnt[a][b] == curr && sum(a, b) == 0) sol++;
}
}
llint count_rectangles (vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = A[i][j];
}
}
for (int r = 0; r < n; r++) precompute_row(r);
for (int r1 = 0; r1 < n; r1++) {
memset(cnt, 0, sizeof cnt);
curr = 0;
for (int c = 0; c < m; c++) {
mn[c] = INF;
}
for (int r2 = r1 + 2; r2 < n; r2++) {
for (int c = 0; c < m; c++) {
mn[c] = min(mn[c], a[r2 - 1][c]);
if (mn[c] < a[r1][c] && mn[c] < a[r2][c]) ok[c] = 0; else ok[c] = 1;
if (c > 0) ok[c] += ok[c - 1];
}
curr++;
add_row(r2 - 1);
}
}
return sol;
}