Submission #1344436

#TimeUsernameProblemLanguageResultExecution timeMemory
1344436osmiyumBob (COCI14_bob)C++20
72 / 120
81 ms4400 KiB
//#pragma GCC optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Alllahuekber
//osmiyum
//23orz
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//dört böler altı artı iki ama ne böler altı ne böler iki
//Başarı, Boş Duranın Hakkı Değil... Koşturanın Hakkıdır. Hakan?
//Ne yapayım, elimden gelen bu :(
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
/* #define int long long */
#define pb push_back
#define ins insert
#define mid ((start+end)/2)
#define FOR for(int i=0;i<n;i++)
#define see2(x,y) cin>>x>>y
#define see3(x,y,z) cin>>x>>y>>z
#define ll long long
#define invalid (start>end || start>r || end<l || r<l)
#define fi first
#define se second
#define _ <<" "<<
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int>> piii;
const int INF=1e7;
const int nmax=1e5+1;
const int MOD=1e9+7;
const int big = 1e9;

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n+1,vector<int>(m+1,-1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>grid[i][j];
    }
    int cev=0;
    vector<int> he(n+1,0);
    for(int i=1;i<=n;i++){
        int x=1;
        vector<int> dp(n+1,0);
        while(x<=m){
            int j=x;
            while(j<=m && grid[i][j]==grid[i][x]){he[j]=(grid[i][j]==grid[i-1][j]?he[j]+1:1);j++;}
            stack<int> st;
            /* for(int k=x;k<j;k++)cout<<he[k]<<" ";
            cout<<endl; */
            for(int k=x;k<j;k++){
                int last=-1;
                while(st.size() && he[st.top()]>=he[k]){st.pop();}
                if(st.empty())dp[k]=he[k]*(k-x+1);
                else dp[k]=dp[st.top()]+he[k]*(k-st.top());
                cev+=dp[k];
                st.push(k);
            }
            x=j;
        }
    }
    cout<<cev<<endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /* freopen("xxxxx.in", "r", stdin);
    freopen("xxxxx.out", "w", stdout); */
    int t=1;
    /* cin>>t; */
    while(t--){
        solve();
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...