oj.uz

Submission #530190

# Submission time Handle Problem Language Result Execution time Memory
530190 2022-02-24T18:57:16 Z CaoHuuKhuongDuy Strah (COCI18_strah) C++14
110 / 110
 724 ms 98824 KB 
#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

strah.cpp: In function 'void solve(long long int*)':
strah.cpp:48:9: warning: unused variable 'minn' [-Wunused-variable]
   48 |     int minn=oo;
      |         ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 0 ms 536 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 464 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6276 KB Output is correct
2 Correct 19 ms 6292 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6268 KB Output is correct
2 Correct 19 ms 6224 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6220 KB Output is correct
2 Correct 19 ms 6256 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 35172 KB Output is correct
2 Correct 469 ms 74276 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 63300 KB Output is correct
2 Correct 712 ms 95504 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 40996 KB Output is correct
2 Correct 529 ms 79144 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 28580 KB Output is correct
2 Correct 724 ms 92080 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 95136 KB Output is correct
2 Correct 624 ms 98824 KB Output is correct