이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
vector<pi> findLegalTuple(const vector<int> &v) {
vector<pi> ret;
vector<size_t> seq; // monotonic
size_t sn = 0;
for (size_t i = 0; i < v.size(); i++) {
while (sn >= 1 && v[seq.back()] == v[i]) seq.pop_back(), --sn;
seq.emplace_back(i), ++sn;
// rearrangement
while (sn >= 2 && v[seq[sn - 2]] < v[seq[sn - 1]]) {
auto tmp = seq[sn - 1];
seq.pop_back(), --sn;
seq[sn - 1] = tmp;
if (sn >= 2) ret.emplace_back(seq[sn - 2], seq[sn - 1]);
}
}
return ret;
}
vector<pi> getMaxPos(const vector<int> &v) {
size_t N = v.size();
vector<pi> ret(N, {-1, -1});
for (int i = N - 1; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
if (ret[j].first == -1 && v[i] > v[j]) ret[j].first = i;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (ret[j].second == -1 && v[i] > v[j]) ret[j].second = i;
}
}
return ret;
}
vector<pi> processToIntervals(const vector<pi> &v) {
vector<pi> ret;
for (auto [el, _] : v) {
if (!ret.empty() && ret.back().second == el - 1)
ret.back().second++;
else
ret.emplace_back(el, el);
}
return ret;
}
bool intervalBinarySearch(const vector<pi> &v, pi t) {
const size_t N = v.size();
size_t res = -1;
size_t s = 0, e = N - 1;
while (e - s >= 2) {
size_t m = (s + e) >> 1;
if (v[m].first <= t.first && t.second <= v[m].second) {
res = m;
break;
}
if (v[m].second < t.first) s = m + 1;
if (v[m].first > t.second) e = m - 1;
}
if (v[s].first <= t.first && t.second <= v[s].second) res = s;
if (v[e].first <= t.first && t.second <= v[e].second) res = e;
return res != -1;
}
i64 count_rectangles(vector<vector<int>> a) {
const size_t N = a.size();
const size_t M = a[0].size();
// transpose
vector<vector<int>> b(M, vector<int>(N));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) b[j][i] = a[i][j];
// get Max Position
vector<vector<pi>> aM(N, vector<pi>(M));
vector<vector<pi>> bM(M, vector<pi>(N));
for (int i = 0; i < N; i++) aM[i] = getMaxPos(a[i]);
for (int i = 0; i < M; i++) bM[i] = getMaxPos(b[i]);
// find Legal Tuple && assign
vector<vector<vector<pi>>> aL(M, decltype(aL)::value_type(M));
vector<vector<vector<pi>>> bL(N, decltype(bL)::value_type(N));
for (int i = 0; i < N; i++) {
auto Lg = findLegalTuple(a[i]);
for (auto [l, r] : Lg) aL[l][r].emplace_back(i, 0);
}
for (int i = 0; i < M; i++) {
auto Lg = findLegalTuple(b[i]);
for (auto [l, r] : Lg) bL[l][r].emplace_back(i, 0);
}
for (auto &vec : aL)
for (auto &el : vec) el = processToIntervals(el);
for (auto &vec : bL)
for (auto &el : vec) el = processToIntervals(el);
// Main Logic
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
auto [L, R] = aM[i][j];
auto [T, B] = bM[j][i];
if (L == -1 || R == -1 || T == -1 || B == -1) continue;
if (intervalBinarySearch(aL[L][R], {T + 1, B - 1}) &&
intervalBinarySearch(bL[T][B], {L + 1, R - 1}))
++ans;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'std::vector<std::pair<int, int> > getMaxPos(const std::vector<int>&)':
rect.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int j = i + 1; j < N; j++) {
| ~~^~~
rect.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < N; i++) {
| ~~^~~
rect.cpp: In function 'bool intervalBinarySearch(const std::vector<std::pair<int, int> >&, pi)':
rect.cpp:94:16: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | return res != -1;
| ~~~~^~~~~
rect.cpp: In function 'i64 count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < N; i++)
| ~~^~~
rect.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
104 | for (int j = 0; j < M; j++) b[j][i] = a[i][j];
| ~~^~~
rect.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
110 | for (int i = 0; i < N; i++) aM[i] = getMaxPos(a[i]);
| ~~^~~
rect.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < M; i++) bM[i] = getMaxPos(b[i]);
| ~~^~~
rect.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
117 | for (int i = 0; i < N; i++) {
| ~~^~~
rect.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
121 | for (int i = 0; i < M; i++) {
| ~~^~~
rect.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < N; i++) {
| ~~^~~
rect.cpp:134:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
134 | for (int j = 0; j < M; j++) {
| ~~^~~
# | 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... |