이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
class Fenwick {
vector <int> f;
public:
Fenwick(int n) {
f.resize(n + 1);
}
void update(int x, int val) {
for (x++; x < f.size(); x += x & -x)
f[x] += val;
}
int get(int x) {
int res = 0;
for (x++; x; x -= x & -x)
res += f[x];
return res;
}
int query(int l, int r) {
return get(r) - get(l - 1);
}
};
vector <pii> find_pairs(const vector <int> &arr) {
int n = arr.size();
vector <pii> res;
stack <int> lft, rig;
for (int i = 0; i < n; i++) {
while (!lft.empty() && arr[lft.top()] < arr[i])
lft.pop();
if (!lft.empty() && lft.top() < i - 1)
res.push_back({lft.top(), i});
lft.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!rig.empty() && arr[rig.top()] < arr[i])
rig.pop();
if (!rig.empty() && arr[rig.top()] > arr[i] && rig.top() > i + 1)
res.push_back({i, rig.top()});
rig.push(i);
}
return res;
}
vector <pii> get_blocks(const vector <int> &v, int bound) {
vector <pii> res;
int sz = v.size(), lst = 0;
for (int i = 0; i < sz; i++)
if (i == sz - 1 || v[i + 1] > v[i] + 1) {
res.push_back({max(v[lst] - 1, 0), min(v[i] + 1, bound - 1)});
lst = i + 1;
}
return res;
}
ll count_rectangles(vector <vector <int>> a) {
int N = a.size();
int M = a[0].size();
vector <vector <vector <int>>> rows(M);
for (int j = 0; j < M; j++)
rows[j].resize(M);
for (int i = 0; i < N; i++) {
vector <pii> tmp = find_pairs(a[i]);
for (auto it : tmp)
rows[it.first][it.second].push_back(i);
}
vector <vector <vector <int>>> cols(N);
for (int i = 0; i < N; i++)
cols[i].resize(N);
for (int j = 0; j < M; j++) {
vector <int> curr;
for (int i = 0; i < N; i++)
curr.push_back(a[i][j]);
vector <pii> tmp = find_pairs(curr);
for (auto it : tmp)
cols[it.first][it.second].push_back(j);
}
vector <vector <int>> in(M * M), out(M * M);
for (int i = 0; i < N; i++)
for (int j = i + 2; j < N; j++) {
vector <pii> tmp = get_blocks(cols[i][j], M);
for (auto it : tmp)
for (int k = it.first; k <= it.second; k++) {
in[k * M + it.first].push_back(i * N + j);
out[k * M + it.second].push_back(i * N + j);
}
}
ll sol = 0;
Fenwick loga(N * N);
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++) {
for (auto it : in[i * M + j])
loga.update(it, 1);
vector <pii> tmp = get_blocks(rows[i][j], N);
for (auto it : tmp)
for (int k = it.first; k <= it.second; k++)
sol += loga.query(k * N + it.first, k * N + it.second);
for (auto it : out[i * M + j])
loga.update(it, -1);
}
return sol;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In member function 'void Fenwick::update(int, int)':
rect.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (x++; x < f.size(); x += x & -x)
~~^~~~~~~~~~
# | 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... |