Submission #530190

#TimeUsernameProblemLanguageResultExecution timeMemory
530190CaoHuuKhuongDuyStrah (COCI18_strah)C++14
110 / 110
724 ms98824 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]; bool ban(int x,int y) { return (x>n||x<1||y>m||y<1||!a[x][y]); } 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]]=max(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 (i==2) cout<<s.begin()->second<<endl; 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; } // cout<<it->second<<endl; if (it->second>=i) { e[i]=it->first; // if (i==2) cout<<e[i]<<"sdsd"<<endl; break; } s.erase(it); } s[h[i]]=r[i]; // cout<<minn<<" "<<h[i<<endl; // e[i]=(minn==oo)?0:minn; // minn=min(minn,h[i]); } // if (dem==2) cout<<save[1].size()<<endl; // cout<<e[m]<<endl; 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; } } //cout<<res-tmp<<endl; 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:48:9: warning: unused variable 'minn' [-Wunused-variable]
   48 |     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...