제출 #119092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119092		OptxPrime	Strah (COCI18_strah)	C++11	55 / 110	1078 ms	69788 KiB

strah

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
#include<string.h>

using namespace std;
#define pb push_back
#define mp make_pair



    /// UMJESTO FORMULE PROBATI DP-OM IZRACUNATI!
    /// DP :  DP[X][1] = X*(X+1)/2, PRELAZ : DP[X][Y] = DP[X][Y-1] + X*(X+1)*Y*(Y+1)/4 , RJESENJE NADJEMO: DP VELKI - DP MALI 1 - DP MALI 2. DVA MALA PODJELI KVADRAT U SREDINI

        int maxn=1000000000;
        int n,m;
        char a[2010][2010];
        long long visina[2010];
        long long h[2010][2010];
        int desno[2010][2010],levo[2010][2010];
        long long tree[400010];
        long long treemax[400010];
        long long dp[2010][2010];
        long long res=0;
        vector<int>tmp;

        void upd( int idx, int l, int r, int pos, int val, bool type )
        {
            if( l > pos || r  < pos || l>r  ) return;
            if( l==r ){
                    if(type==0)
                            tree[idx]=val;
            else treemax[idx]=val;
                return;
            }
            int mid=(l+r)/2;
        //cout << (idx << 1) +1 << " " << idx << " samo da znas" <<endl;
            upd( (idx<<1), l ,mid, pos,val,type  );
            upd( ( idx<<1 ) + 1, mid+1,r,pos,val,type );
            if( type==0 )
            tree[idx]=min( tree[ (idx<<1) ], tree[ (idx<<1) + 1 ] );
            else treemax[idx]=max( treemax[ (idx<<1) ], treemax[ ( idx << 1 ) + 1 ] );
        }
        int rmq( int idx, int l, int r, int i, int j, bool type )
        {
            if( l > j || r < i ||  l> r ){
                if( type==1 ) return -1;
                else return maxn;
            }
            if( l >= i && r <= j ){
                if( type ) return treemax[idx];
                else return tree[idx];
            }
            int mid=(l+r)/2;
            int val1=rmq( (idx<<1),l,mid,i,j,type );
            int val2=rmq( ( idx<<1 )+1,mid+1,r,i,j,type );
            if( type==0 ) return min( val1,val2 );
            else return max( val1,val2 );
        }

    void check( int i,int j, bool w )
    {
        long long val=a[i][j];
        if(  val == '#' ){       /// ocistimo fenvikovo
              /*      for( int k=0;k<tmp.size();k++ ){
                        upd( 1,0,n-1,tmp[k], maxn );
                    }*/
         //           visina[j] = (long long)(n-i-1); /// nova pregrada znaci novo ogranicenje za visinu
         if( w==0 )
         visina[j]=i;
         upd( 1,0,n,0, j,1-w  );    /// 1-w, jer ako je w= 0 trazimo max, a max je 1 i obratno
         tmp.pb( 0 );
                }
                else{       /// inace, dodamo na rezultat pa dodamo u fenwikovo
                    if( w==0 )
                        h[i][j] = i-visina[j];
          //          h[i][j]= i-visina[j];     /// treba jos skontat kako update visinu

           //     if( i==0 && j == 2 ) cout << visina[j] << " wtf " << h[i][j]<<endl;
                    ///     upd( 1,0,n-1, h[i][j], j );  /// upd prije ili poslije?!
               if(w)    {
                   // }

                    desno[i][j] = rmq( 1,0,n,0, h[i][j]-1,0 ); /// desno udara strogo u manje, a lijevo udara i u isti.. NE NADJE DOBRO DESNI, NE ZNAM STO
                    desno[i][j] = min( desno[i][j], m );
                //    tmp.pb( h[i][j] );
               }
               else{
        //            if( i == 0 && j == 2 ) cout << rmq( 1,0,n,0,0,1 ) << " eee e" <<endl;
                 levo[i][j] = rmq( 1,0,n, 0, h[i][j] ,1 );   /// 1 je za max, 0 je za min
                 if( levo[i][j] == maxn ) levo[i][j]=-1;
            //     tmp.pb( h[i][j] );
               }
        //       if( w && i==0 && j==2 ) cout << h[i][j] << " begee " <<endl;
            upd( 1,0,n, h[i][j], j,1-w );
            tmp.pb( h[i][j] );
            }
    }


int main()
{

        cin>>n>>m;
        for( long long i=1;i<=n;i++ ) dp[i][1] = (i*(i+1))/2;
        for( long long i=1;i<=n;i++ ){
            for( long long j=2;j<=m;j++ ) dp[i][j] = dp[i][j-1] + ( i*(i+1)*j*(j+1) )/4;
        }
   //     cout << dp[n][m] <<endl;
    //    cout << dp[3][2] << " " << dp[3][3] << " bezi ba"  <<endl;
     //   cout << dp[1][1] << " oko " <<endl;


        for( int i=0;i<= 4*(n+1);i++ ) tree[i] = maxn;
        for( int i=0;i<=4*(n+1);i++ ) treemax[i]=-1;
        for( int i=0;i<m;i++ ) visina[i]=-1;
        for( int i=0;i<n;i++ ){
            for( int j=0;j<m;j++ ){
                cin>>a[i][j];
                check( i,j,0 );
            }
            /// kad god predjemo u novi red, takodjer treba obrisati fenvikovo
            for( int k=0;k<tmp.size();k++ ) {
                    upd( 1,0,n,tmp[k],-1,1 );
            }
            tmp.clear();
        }
    //     cout << rmq( 1,0,n-1,0,n ) << " bolaaaaa " <<endl;
       //  for( int i=0;i<m;i++ ) visina[i]=-1; /// resetujemo visine
        for( int i=0;i<n;i++ ){
            for( int j=m-1;j>=0;j-- ){
                check( i,j,1 );
            }
            /// kad god predjemo u novi red, takodjer treba obrisati fenvikovo
           for( int k=0;k<tmp.size();k++ ) upd( 1,0,n,tmp[k],maxn,0 );
           tmp.clear();
    //  for( int i=0;i<=4*n;i++ ) tree[i]=maxn;
        }
       // cout << rmq( 1,0,n-1,0,n ) << " bolaaaaa " <<endl;
        for( int i=0;i<n;i++ ){
            for( int j=0;j<m;j++ ){
             //   h[i][j] -= (n-i-1) ;
             if( a[i][j] == '#' ) continue;

                long long a= (long long)(desno[i][j] - levo[i][j] - 1);
                long long b= ( long long ) h[i][j];
                long long mali1 = desno[i][j] - j-1;
                long long mali2 = j - levo[i][j]-1;
                /// ovdje sad ide formula za onaj pravougaonik koju moram izracunat jos na papiru
                res+= dp[b][a];
                res-= dp[ b ][mali1];
                res-=dp[b][mali2];
            }
        }

        cout<<res<<endl;
        ///moram dodat njih same, to sam zaboravio
}

/*
5
1
2
1

2
2
*/

컴파일 시 표준 에러 (stderr) 메시지

strah.cpp: In function 'int main()':
strah.cpp:125:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for( int k=0;k<tmp.size();k++ ) {
                          ~^~~~~~~~~~~
strah.cpp:137:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
            for( int k=0;k<tmp.size();k++ ) upd( 1,0,n,tmp[k],maxn,0 );
                         ~^~~~~~~~~~~

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