Submission #530191

#TimeUsernameProblemLanguageResultExecution timeMemory
530191CaoHuuKhuongDuyStrah (COCI18_strah)C++14
110 / 110
727 ms95024 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair <int,int> ii; const int N=2e3+9; const int oo=1e9+9; char c; int a[N][N]; int n,m,l[N],r[N],h[N][N],pf[N][N],e[N],res=0,dem=0,tmp=0; map <int,int> save[N]; int cal(int n,int m) { int fi=((1+m)*m)/2; int last=n*fi; return (last+fi)*n/2; } void solve(int h[]) { stack <int> q; h[0]=-1; q.push(0); for (int i=1;i<=m;i++) { while (h[i]<=h[q.top()]) q.pop(); l[i]=q.top()+1; q.push(i); } while (!q.empty()) q.pop(); h[m+1]=-1; q.push(m+1); for (int i=m;i>=1;i--) { while (h[i]<=h[q.top()]) q.pop(); r[i]=q.top()-1; q.push(i); } for (int i=1;i<=m;i++) if (h[i]!=0) save[l[i]][h[i]]=r[i]; map <int,int,greater<int> > s; int back; dem++; int minn=oo; for (int i=1;i<=m;i++) { if (h[i]==0) { s.clear(); continue; } if (!save[i].size()) { s[h[i]]=r[i]; continue; } while (true) { auto it=s.upper_bound(save[i].begin()->first); if (it==s.end()) { e[i]=0; break; } if (it->second>=i) { e[i]=it->first; break; } s.erase(it); } s[h[i]]=r[i]; } for (int i=1;i<=m;i++) { back=e[i]; for (auto &xnew:save[i]) { res+=pf[xnew.first][xnew.second-i+1]-pf[back][xnew.second-i+1]; back=xnew.first; } } tmp=res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("test.inp","r",stdin); // freopen("check1.out","w",stdout); cin>>n>>m; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { cin>>c; a[i][j]=(c=='.'); } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) h[i][j]=((!a[i][j])?0:(h[i-1][j]+1)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) pf[i][j]=pf[i][j-1]+cal(i,j); for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) save[j].clear(); solve(h[i]); } cout<<res; return 0; }

Compilation message (stderr)

strah.cpp: In function 'void solve(long long int*)':
strah.cpp:42:9: warning: unused variable 'minn' [-Wunused-variable]
   42 |     int minn=oo;
      |         ^~~~
#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...