#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(10);
int Tests = 1; // cin >> Tests;
while (Tests --) {
int N, M; cin >> N >> M;
vector<vector<int>> a(N + 2, vector<int> (M + 2, 0));
vector<vector<int>> h(N + 2, vector<int> (M + 2, 0));
vector<vector<i64>> f(N + 2, vector<i64> (M + 2, 0));
for (int i = 1; i <= N; i ++) {
for (int j = 1; j <= M; j ++) {
cin >> a[i][j];
}
}
for (int j = 1; j <= M; j ++) {
for (int i = 1; i <= N; i ++) {
if (a[i][j] != a[i - 1][j]) h[i][j] = 1;
else h[i][j] = h[i - 1][j] + 1;
}
}
i64 ans = 0;
stack<int> st;
for (int i = 1; i <= N; i ++) {
while (!st.empty()) st.pop();
for (int j = 1; j <= M; j ++) {
if (a[i][j] != a[i][j - 1]) {
while (!st.empty()) st.pop();
f[i][j] = h[i][j];
ans += f[i][j];
h[i][j - 1] = 0;
f[i][j - 1] = 0;
st.push(j - 1);
st.push(j);
continue;
}
while (!st.empty() && h[i][st.top()] >= h[i][j]) st.pop();
f[i][j] = f[i][st.top()] + (j - st.top()) * h[i][j];
ans = ans + f[i][j];
st.push(j);
}
}
cout << ans << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
4440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
4440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
16220 KB |
Output is correct |
2 |
Correct |
46 ms |
18012 KB |
Output is correct |
3 |
Correct |
50 ms |
18108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
16260 KB |
Output is correct |
2 |
Correct |
48 ms |
18068 KB |
Output is correct |
3 |
Correct |
46 ms |
18040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
16216 KB |
Output is correct |
2 |
Correct |
46 ms |
18008 KB |
Output is correct |
3 |
Correct |
45 ms |
18008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
16264 KB |
Output is correct |
2 |
Correct |
46 ms |
18040 KB |
Output is correct |
3 |
Correct |
45 ms |
18000 KB |
Output is correct |