Submission #197872

#TimeUsernameProblemLanguageResultExecution timeMemory
197872Osama_AlkhodairyStrah (COCI18_strah)C++17
110 / 110
323 ms28388 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long const int N = 2001; int n, m, g[N][N], p[N], sz[N], h[N]; vector <string> a; vector <int> v[N]; ll sum; ll f(int x){ return 1LL * x * (x + 1) * (x + 2) / 6; } int find(int x){ if(p[x] == x) return x; return p[x] = find(p[x]); } void merge(int x, int y){ x = find(x); y = find(y); sz[y] += sz[x]; p[x] = y; } void add(int x){ h[x] = 1; if(x > 0 && h[x - 1]){ sum -= f(sz[find(x - 1)]); merge(x - 1, x); } if(x < n - 1 && h[x + 1]){ sum -= f(sz[find(x + 1)]); merge(x, x + 1); } sum += f(sz[find(x)]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; a.resize(n); for(auto &i : a) cin >> i; for(int i = 0 ; i < n ; i++){ g[i][m] = m; for(int j = m - 1 ; j >= 0 ; j--){ g[i][j] = g[i][j + 1]; if(a[i][j] == '#') g[i][j] = j; } } ll ans = 0; for(int col1 = 0 ; col1 < m ; col1++){ sum = 0; for(int row = 0 ; row < n ; row++){ v[g[row][col1]].push_back(row); h[row] = 0; p[row] = row; sz[row] = 1; } for(int col2 = m ; col2 > col1 ; col2--){ for(auto &i : v[col2]) add(i); v[col2].clear(); ans += sum * (col2 - col1); } } cout << ans << 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...