oj.uz

Submission #332781

# Submission time Handle Problem Language Result Execution time Memory
332781 2020-12-03T10:58:00 Z vitkishloh228 Strah (COCI18_strah) C++14
110 / 110
 270 ms 71020 KB 
#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])*((i-arr1[i][0])+1)/2)));
    ans1+=ans;
    lli arr2[m]={},ans2[m];
    arr2[0]=dp[1][i-arr1[i][0]];
    ans2[0]=ans;
    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;
      ans2[j]=ans;
      s.push(mp(mp(c,j),mp(i-arr1[i][j],v+(i-arr1[i][j]+1)*(i-arr1[i][j])*(j-c+1)/2)));
    }
    while(s.size())
      s.pop();
  }
  cout<<ans1<<endl;
  return(0);
}

Compilation message

strah.cpp: In function 'int main()':
strah.cpp:59:20: warning: variable 'ans2' set but not used [-Wunused-but-set-variable]
   59 |     lli arr2[m]={},ans2[m];
      |                    ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31744 KB Output is correct
2 Correct 32 ms 31724 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31724 KB Output is correct
2 Correct 28 ms 31724 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 34284 KB Output is correct
2 Correct 36 ms 34284 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 34284 KB Output is correct
2 Correct 32 ms 34284 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 34284 KB Output is correct
2 Correct 33 ms 34284 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 45932 KB Output is correct
2 Correct 186 ms 60652 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 57580 KB Output is correct
2 Correct 255 ms 69484 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 48236 KB Output is correct
2 Correct 188 ms 62572 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 44908 KB Output is correct
2 Correct 202 ms 67692 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 70892 KB Output is correct
2 Correct 270 ms 71020 KB Output is correct