이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2505;
ll res = 0;
int N, M;
int L[MAXN], R[MAXN];
stack<int> S;
map<pair<int,int>,int> mapa[MAXN];
vector<pair<int,int>> getinterval(vector<int> &V){
vector<pair<int,int>> res;
while (!S.empty())
S.pop();
S.push(0);
L[0] = -1;
for (int i = 1; i < V.size(); i++) {
while (!S.empty() && V[S.top()] <= V[i])
S.pop();
if (S.empty())
L[i] = -1;
else
L[i] = S.top() + 1;
S.push(i);
}
while (!S.empty())
S.pop();
S.push(V.size() - 1);
for (int i = V.size() - 2; i >= 1; i--) {
while (!S.empty() && V[S.top()] <= V[i])
S.pop();
if (S.empty())
R[i] = -1;
else
R[i] = S.top() - 1;
S.push(i);
}
for (int i = 1; i < V.size() - 1; i++) {
if (L[i] == -1 || R[i] == -1)
continue;
res.push_back({L[i], R[i]});
}
if (res.size()) {
sort(res.begin(), res.end());
vector<pair<int,int>> r2;
r2.push_back(res[0]);
for (int i = 1; i < res.size(); i++)
if (res[i] != res[i - 1])
r2.push_back(res[i]);
return r2;
}
return res;
}
struct slog {
int duz, kol;
};
bool poduz(slog a, slog b) {
return a.duz < b.duz;
}
bool pokol(slog a, slog b) {
return a.kol < b.kol;
}
vector<slog> vert[MAXN][MAXN];
int fwt[MAXN];
void add(int x, int kol) {
x++;
for (int i = x; i <= MAXN; i += i & -i)
fwt[i] += kol;
}
int sum(int x) {
int r = 0;
x++;
for (int i = x; i >= 1; i -= i & -i)
r += fwt[i];
return r;
}
ll resi(vector<slog> &A, vector<slog> &B) {
ll ret = 0;
sort(A.begin(), A.end(), poduz);
sort(B.begin(), B.end(), pokol);
for (int i = 0; i < B.size(); i++)
add(B[i].duz, 1);
int pok = 0;
for (int i = 0; i < A.size(); i++) {
while (pok < B.size() && B[pok].kol < A[i].duz) {
add(B[pok].duz, -1);
pok++;
}
ret += sum(A[i].kol);
}
while (pok < B.size()) {
add(B[pok].duz, -1);
pok++;
}
return ret;
}
ll count_rectangles(vector<vector<int>> inp) {
N = inp.size();
M = inp[0].size();
for (int i = N - 2; i >= 1; i--) {
vector<int> V;
for (int j = 0; j < M; j++)
V.push_back(inp[i][j]);
auto I = getinterval(V);
for (auto x : I) {
if (mapa[i + 1].find(x) != mapa[i + 1].end())
mapa[i][x] = mapa[i + 1][x] + 1;
else
mapa[i][x] = 1;
slog pp;
pp.kol = mapa[i][x];
pp.duz = x.second - x.first + 1;
vert[i][x.first].push_back(pp);
}
}
ll res = 0;
for (int i = M - 2; i >= 1; i--) {
vector<int> V;
for (int j = 0; j < N; j++)
V.push_back(inp[j][i]);
auto I = getinterval(V);
if (I.size() == 0)
continue;
vector<slog> PV;
int px = I[0].first;
for (auto x : I) {
if (x.first != px) {
res += resi(vert[px][i], PV);
px = x.first;
PV.clear();
}
if (mapa[i + 1].find(x) != mapa[i + 1].end())
mapa[i][x] = mapa[i + 1][x] + 1;
else
mapa[i][x] = 1;
slog pp;
pp.kol = mapa[i][x];
pp.duz = x.second - x.first + 1;
PV.push_back(pp);
}
res += resi(vert[px][i], PV);
}
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'std::vector<std::pair<int, int> > getinterval(std::vector<int>&)':
rect.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 1; i < V.size(); i++) {
| ~~^~~~~~~~~~
rect.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 1; i < V.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~
rect.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 1; i < res.size(); i++)
| ~~^~~~~~~~~~~~
rect.cpp: In function 'long long int resi(std::vector<slog>&, std::vector<slog>&)':
rect.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0; i < B.size(); i++)
| ~~^~~~~~~~~~
rect.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 0; i < A.size(); i++) {
| ~~^~~~~~~~~~
rect.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while (pok < B.size() && B[pok].kol < A[i].duz) {
| ~~~~^~~~~~~~~~
rect.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while (pok < B.size()) {
| ~~~~^~~~~~~~~~
# | 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... |