Submission #1013424

#TimeUsernameProblemLanguageResultExecution timeMemory
1013424Khanhcsp2Bob (COCI14_bob)C++14
120 / 120
116 ms18036 KiB
#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(); } }
#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...