이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
struct BIT {
vt<int> fen;
BIT(int n) {
fen.resize(n);
}
void upd(int i, int v) {
for (; i < size(fen); i += i+1 & -i-1)
fen[i] += v;
}
int qry(int i) {
int ret = 0;
for (; i >= 0; i -= i+1 & -i-1)
ret += fen[i];
return ret;
}
int qry(int l, int r) {
return r < l ? 0 : qry(r) - qry(l-1);
}
};
ll count_rectangles(vt<vt<int>> A) {
const int N = size(A), M = size(A[0]);
int X[N][M], Y[N][M];
FOR(i, 0, N-1) {
vt<int> sk;
FOR(j, 0, M-1) {
while (size(sk) && A[i][sk.back()] < A[i][j])
sk.pop_back();
X[i][j] = size(sk) ? sk.back() + 1 : 0;
sk.push_back(j);
}
sk.clear();
ROF(j, M-1, 0) {
while (size(sk) && A[i][sk.back()] < A[i][j])
sk.pop_back();
Y[i][j] = size(sk) ? sk.back() - 1 : M - 1;
sk.push_back(j);
}
}
#ifdef DEBUG
cout << "X:\n";
FOR(i, 0, N-1)
FOR(j, 0, M-1)
cout << X[i][j] << "\n "[j+1<M];
cout << "Y:\n";
FOR(i, 0, N-1)
FOR(j, 0, M-1)
cout << Y[i][j] << "\n "[j+1<M];
#endif
ll ans = 0;
int R[M], L[M], mx[M];
FOR(l, 1, N-2) {
memset(R, 0x3f, sizeof(R));
memset(L, 0xc0, sizeof(L));
memset(mx, 0xc0, sizeof(mx));
FOR(r, l, N-2) {
BIT fen(M);
multiset<ari2> ma;
multiset<int> mb;
int dead_bef = 0;
FOR(i, 0, M-1) {
while (size(ma)) {
auto [a, b] = *begin(ma);
if (a >= i-1)
break;
ma.erase(begin(ma));
mb.erase(mb.find(b));
fen.upd(b, -1);
}
while (size(mb)) {
int a = *begin(mb);
if (a >= dead_bef)
break;
mb.erase(begin(mb));
ma.erase(ma.find({R[a], a}));
fen.upd(a, -1);
}
R[i] = min(R[i], Y[r][i]);
L[i] = max(L[i], X[r][i]);
mx[i] = max(mx[i], A[r][i]);
if (i && mx[i-1] < min(A[l-1][i-1], A[r+1][i-1])) {
ans += fen.qry(L[i]-1, i-2);
#ifdef DEBUG
cout << "contribution from " << i-1 << ' ' << l << ' ' << r << ": " << fen.qry(L[i]-1, i-2) << '\n';
#endif
} else {
dead_bef = i - 1;
}
ma.insert({R[i], i});
mb.insert(i);
fen.upd(i, 1);
}
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In member function 'void BIT::upd(int, int)':
rect.cpp:23:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
23 | for (; i < size(fen); i += i+1 & -i-1)
| ~^~
rect.cpp: In member function 'int BIT::qry(int)':
rect.cpp:28:26: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
28 | for (; i >= 0; i -= i+1 & -i-1)
| ~^~
# | 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... |