Submission #256906

#	Time	Username	Problem	Language	Result	Execution time	Memory
256906		uacoder123	Strah (COCI18_strah)	C++14	0 / 110	250 ms	70748 KiB

strah

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
  
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
char arr[2000][2000];
lli arr1[2000][2000],dp[2001][2001]={};
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli n,m;
  cin>>n>>m;
  for(lli i=0;i<n;++i)
    for(lli j=0;j<m;++j)
      cin>>arr[i][j];
  for(lli j=0;j<m;++j)
  {
    lli c=-1;
    for(lli i=0;i<n;++i)
    {
      if(arr[i][j]=='#')
      {
        arr1[i][j]=i;
        c=i;
      }
      else
        arr1[i][j]=c;
    }
  }
  for(lli i=1;i<=2000;++i)
  {
    for(lli j=1;j<=2000;++j)
    {
      dp[i][j]=dp[i][j-1]+(i)*(i+1)*(j)/2;
    }
  }
  stack<pair<ii,ii>> s;
  lli ans1=0,ans=0;
  for(lli i=0;i<n;++i)
  {
    ans=dp[1][i-arr1[i][0]];
    s.push(mp(mp(0,0),mp(i-arr1[i][0],i-arr1[i][0])));
    ans1+=ans;
    lli arr2[m]={};
    arr2[0]=dp[1][i-arr1[i][0]];
    for(lli j=1;j<m;++j)
    {
      lli c=j,v=0;
      while(s.size())
      {
        if(s.top().S.F>=(i-arr1[i][j]))
        {
          ans-=arr2[s.top().F.S];
          c-=s.top().F.S-s.top().F.F+1;
          s.pop();
        }
        else
          break;
      }
      if(s.size())
      {
        v=s.top().S.S;
        ans+=(v)*(j-s.top().F.S);
        arr2[j]+=(v)*(j-s.top().F.S);
      }
      ans+=dp[j-c+1][(i-arr1[i][j])];
      arr2[j]+=dp[j-c+1][(i-arr1[i][j])];
      ans1+=ans;
      v+=(j-c+1)*(i-arr1[i][j]);
      s.push(mp(mp(c,j),mp((i-arr1[i][j]),v)));
    }
    while(s.size())
      s.pop();
  }
  cout<<ans1<<endl;
  return(0);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11