Submission #365805

#TimeUsernameProblemLanguageResultExecution timeMemory
365805maozkurtBob (COCI14_bob)C++17
120 / 120
168 ms25964 KiB
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #include <string> #include <stack> #include <numeric> #include <cassert> #define endl '\n' #define sp ' ' #define pb push_back #define mp make_pair #define ff first #define ss second using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int maxn = 1005; int arr[maxn][maxn]; int h[maxn][maxn]; ll ans[maxn][maxn]; int main(){ ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr); int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>arr[i][j]; } for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ if(arr[i-1][j] == arr[i][j]){ h[i][j] = h[i-1][j] + 1; } else h[i][j] = 1; } } deque<pii> q; for(int i=1;i<=n;i++){ q.clear(); for(int j=1;j<=m;j++){ if(arr[i][j-1] != arr[i][j]){ q.clear(); q.push_front({-1,j-1}); } while(q.size() && h[i][j] <= q.front().ff) q.pop_front(); int cur = q.front().ss; q.push_front({h[i][j],j}); ans[i][j] = (ll)(j-cur) * h[i][j] + (arr[i][cur] == arr[i][j] ? ans[i][cur] : 0); } } ll aa = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ aa += ans[i][j]; } } cout << aa << endl; /* for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cerr << ans[i][j] << sp; } cerr << endl; } cerr << endl; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cerr << h[i][j] << sp; } cerr << endl; } */ }
#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...