Submission #582537

#TimeUsernameProblemLanguageResultExecution timeMemory
582537vuavisaoBob (COCI14_bob)C++14
84 / 120
1079 ms17936 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define ll long long using namespace std; const int N = 1e3 + 10; int n, m; int a[N][N]; int nxt[N][N]; int h[N]; int l[N], r[N]; ll res; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("BOB.inp", "r", stdin); // freopen("BOB.out", "w", stdout); cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j]; for(int _ = 1; _ <= n; _++) for(int l = 1, r = 1; l <= m;) { while(r <= n && a[_][r] == a[_][l]) r++; nxt[_][l] = r; l = r; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { h[j] = (a[i][j] == a[i - 1][j] ? h[j] + 1 : 1); l[i] = 0; r[i] = 0; } for(int j = 1; j <= m; j = nxt[i][j]) { stack<int> stk; for(int k = j; k < nxt[i][j]; k++) { while(!stk.empty() && h[stk.top()] >= h[k]) stk.pop(); if(stk.empty()) l[k] = j; else l[k] = stk.top() + 1; stk.push(k); } while(!stk.empty()) stk.pop(); for(int k = nxt[i][j] - 1; k >= j; k--) { while(!stk.empty() && h[stk.top()] > h[k]) stk.pop(); if(stk.empty()) r[k] = nxt[i][j] - 1; else r[k] = stk.top() - 1; stk.push(k); } } for(int j = 1; j <= m; j++) res += 1ll * h[j] * (j - l[j] + 1) * (r[j] - j + 1); } cout << res; return 0; } /// Code by vuavisao
#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...