oj.uz

Submission #1013424

# Submission time Handle Problem Language Result Execution time Memory
1013424 2024-07-03T14:14:49 Z Khanhcsp2 Bob (COCI14_bob) C++14
120 / 120
 116 ms 18036 KB 
#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e3+11;
int m, n, a[N][N], h[N], nx[N], pre[N], ans=0;
void calc(int l, int r)
{
    stack<int> st;
    for(int i=l; i<=r; i++)
    {
        while(!st.empty() && h[i]<h[st.top()]) st.pop();
        if(!st.empty()) pre[i]=st.top()+1;
        else pre[i]=l;
        st.push(i);
    }
//    st.clear();
    while(!st.empty()) st.pop();
    for(int i=r; i>=l; i--)
    {
        while(!st.empty() && h[i]<=h[st.top()]) st.pop();
        if(!st.empty()) nx[i]=st.top()-1;
        else nx[i]=r;
        ans+=h[i]*(nx[i]-i+1)*(i-pre[i]+1);
        st.push(i);
    }
}
void sol()
{
    cin >> m >> n;
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(a[i-1][j]==a[i][j]) h[j]++;
            else h[j]=1;
        }
        int run=1;
        for(int j=1;j<=n+1;j++)
        {
            if(a[i][run]!=a[i][j]) calc(run, j-1), run=j;
        }
    }
    cout << ans;
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5212 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5468 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5848 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5720 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 14928 KB Output is correct
2 Correct 40 ms 10324 KB Output is correct
3 Correct 39 ms 10324 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 18036 KB Output is correct
2 Correct 57 ms 10320 KB Output is correct
3 Correct 42 ms 10276 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 17740 KB Output is correct
2 Correct 39 ms 10204 KB Output is correct
3 Correct 44 ms 10080 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 17996 KB Output is correct
2 Correct 42 ms 10316 KB Output is correct
3 Correct 40 ms 10332 KB Output is correct