| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1071573 |
2024-08-23T08:58:02 Z |
TrinhKhanhDung |
Bob (COCI14_bob) |
C++14 |
|
94 ms |
18524 KB |
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define v1 vector<ll>
#define v2 vector<vector<ll>>
#define MAX (int)(2003)
#define limit (int)(100003)
#define MOD (ll)(1000000007)
#define INF (int)1e9
#define oo (ll)MASK(62)
template <class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template <class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
using namespace std;
int nRow, nCol;
int board[MAX][MAX];
void sub2()
{
ll ans = 0;
for(int u=1; u<=nRow; u++){
vector<int> a(nCol + 3);
for(int i=1; i<=nCol; i++) a[i] = board[u][i];
int dem = 0;
for(int d=u; d<=nRow; d++){
for(int i=1; i<=nCol; i++){
if(a[i] == -1) continue;
if(board[d][i] != board[u][i]){
a[i] = -1;
dem++;
}
}
if(dem == nCol) break;
int cnt = 0;
for(int i=1; i<=nCol; i++){
cnt++;
if(i == nCol || a[i] != a[i + 1]){
if(a[i] != -1){
ans += 1ll * cnt * (cnt + 1) / 2;
}
cnt = 0;
}
}
}
}
cout << ans;
}
int h[MAX];
void sub4()
{
ll ans = 0;
for(int i=1; i<=nRow; i++){
for(int j=1; j<=nCol; j++){
if(board[i][j] == board[i-1][j]) h[j]++;
else h[j] = 1;
}
vector<int> L(nCol + 3, 0), R(nCol + 3, 0);
stack<int> st;
int tmp = 0;
for(int j=1; j<=nCol; j++){
while(!st.empty() && h[st.top()] >= h[j]) st.pop();
if(st.empty()) L[j] = tmp;
else L[j] = st.top();
st.push(j);
if(j == nCol || board[i][j] != board[i][j + 1]){
while(!st.empty()) st.pop();
tmp = j;
}
}
tmp = nCol + 1;
for(int j=nCol; j>=1; j--){
while(!st.empty() && h[st.top()] > h[j]) st.pop();
if(st.empty()) R[j] = tmp;
else R[j] = st.top();
st.push(j);
if(j == 1 || board[i][j] != board[i][j-1]){
while(!st.empty()) st.pop();
tmp = j;
}
}
for(int j=1; j<=nCol; j++){
ans += 1ll * h[j] * (j - L[j]) * (R[j] - j);
}
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> nRow >> nCol;
for(int i=1; i<=nRow; i++){
for(int j=1; j<=nCol; j++){
cin >> board[i][j];
}
}
sub4();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
5468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
5824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
5724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
15316 KB |
Output is correct |
| 2 |
Correct |
44 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
44 ms |
10608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
18524 KB |
Output is correct |
| 2 |
Correct |
46 ms |
10732 KB |
Output is correct |
| 3 |
Correct |
41 ms |
10580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
18148 KB |
Output is correct |
| 2 |
Correct |
41 ms |
10580 KB |
Output is correct |
| 3 |
Correct |
45 ms |
10600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
18516 KB |
Output is correct |
| 2 |
Correct |
44 ms |
10580 KB |
Output is correct |
| 3 |
Correct |
43 ms |
10580 KB |
Output is correct |
