Submission #83492

#	Time	Username	Problem	Language	Result	Execution time	Memory
83492		ToadDaveski	UFO (IZhO14_ufo)	C++14	5 / 100	2088 ms	263168 KiB

ufo

#include <bits/stdc++.h>
#define ll long long
using namespace std;
map <ll,map <ll,ll> > h,v,a,ans,dp;
void build(ll x,ll l,ll r,ll type,ll i)
{
    if (l==r)
    {
        //cout<<"| ";
        if (type==1){
            h[i][x]=a[i][l];
            //cout<<h[i][x]<<" h "<<i<<" "<<l;
        }
        else {
            v[i][x]=a[l][i];
            //cout<<v[i][x]<<" v "<<l<<" "<<i;
        }
        //cout<<endl;
    }
    else
    {
        ll bm=(l+r)/2;
        build(x*2,l,bm,type,i);
        build(x*2+1,bm+1,r,type,i);
        if (type==1)
            h[i][x]=max(h[i][x*2],h[i][x*2+1]);
        else   v[i][x]=max(v[i][x*2],v[i][x*2+1]);
    }
}
ll findans(ll x,ll l,ll r,ll tl, ll tr,ll i,ll height,ll type)
{
    //cout<<x<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<i<<" "<<type<<" ";
    //if (type<=2) cout<<h[i][x]<<endl;
    //else cout<<v[i][x]<<endl;
    if (type<=2 && h[i][x]<height)
        if (type==1)  return 1e12;
        else return -1;
    if (type>=3 && v[i][x]<height)
        if (type==3) return 1e12;
        else return -1;

    if (l==r)
    {
        if (type<=2){
            if (h[i][x]>=height)
                {
        //            cout<<"nashelnahui "<<l<<endl;
                    if (tl==l) return l;
                    if (type==1) return 1e9;
                    else return -1;
                }
        }
        else{
            if (v[i][x]>=height)
                {
      //              cout<<"nashelnahui "<<l<<endl;
                    if (tl==l) return l;
                    if (type==3) return 1e9;
                    else return -1;
                }
        }
        return -1;
    }
    ll bm=(l+r)/2;
    //cout<<"zaebalblyat";
    if (type==1 || type==3)
        return min(findans(x*2,l,bm,tl,min(bm,tr),i,height,type),findans(x*2+1,bm+1,r,max(tl,bm+1),tr,i,height,type));
    if (type==2 || type==4)
        return max(findans(x*2,l,bm,tl,min(bm,tr),i,height,type),findans(x*2+1,bm+1,r,max(tl,bm+1),tr,i,height,type));
}
void update(ll x,ll l,ll r,ll i,ll poz,ll type)
{
    //cout<<l<<" update "<<r<<" "<<poz<<endl;
    if (l==r)
    {
        if (type==1)
            h[i][x]--;
        else v[i][x]--;
        //cout<<"#"<<l<<" update "<<h[i][x]<<" "<<v[i][x]<<endl;
    }
    else
    {
        ll bm=(l+r)/2;
        if (l<=poz && poz<=bm)
            update(x*2,l,bm,i,poz,type);
        else update(x*2+1,bm+1,r,i,poz,type);
        if (type==1)
            h[i][x]=max(h[i][x*2],h[i][x*2+1]);
        else   v[i][x]=max(v[i][x*2],v[i][x*2+1]);
    }
}
void  makeup(ll x,ll l,ll r,ll i)
{
    if (l==r)
    {
        ans[l][i]=v[i][x];
       // cout<<v[i][x]<<"#"<<endl;
    }
    else
    {
        ll bm=(l+r)/2;
        makeup(x*2,l,bm,i);
        makeup(x*2+1,bm+1,r,i);
    }
}
int main()
{
    ll n,m,R,k,P,i,j;
    cin>>n>>m>>R>>k>>P;
    //k--;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        ll x;
        cin>>x;
        a[i][j]=x;
    }
    for(i=1;i<=n;i++)
        build(1,1,m,1,i);
    for(i=1;i<=m;i++)
        build(1,1,n,2,i);
    //cout<<3<<endl;
    while(k--)
    {
        char c;
        ll type;
        cin>>c;
        if (c=='W') type=1;
        if (c=='E') type=2;
        if (c=='N') type=3;
        if (c=='S') type=4;
        ll x,y;
        cin>>x>>y;
        if (type==1 || type==2)
        {
            ll tl=1,tr=m;
            for(j=1;j<=R;j++)
            {
                ll f=findans(1,1,m,tl,tr,x,y,type);
        //        cout<<f<<endl;
                if (f==-1 || f==1e12) continue;
                update(1,1,m,x,f,1);
                update(1,1,n,f,x,2);
                if (type==1) tl=f+1;
                else tr=f-1;
            }
        }
        if (type==3 || type==4)
        {
            ll tl=1,tr=n;
            for(j=1;j<=R;j++)
            {
      //          cout<<3<<endl;
                ll f=findans(1,1,n,tl,tr,x,y,type);
                if (f==-1 || f==1e12) continue;
                update(1,1,n,x,f,2);
                update(1,1,m,f,x,1);
                if (type==3) tl=f+1;
                else tr=f-1;
            }
        }
    }
    for(i=1;i<=m;i++)
         makeup(1,1,n,i);
    for(i=1;i<=n;i++)
    {
        ll sum=0;
        for(j=1;j<=m;j++)
        {
            sum+=ans[i][j];
            dp[i][j]=dp[i-1][j]+sum;
        }
    }
    //cout<<endl;
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }*/
    ll answer=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
    {
      //  cout<<dp[i][j]<<" ";
        if (i<P || j<P)
            continue;
        answer=max(answer,dp[i][j]-(dp[i][j-P]+dp[i-P][j]-dp[i-P][j-P]));
    }
    //cout<<endl;
    }
    cout<<answer;
    return 0;
}

Compilation message (stderr)

ufo.cpp: In function 'long long int findans(long long int, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
ufo.cpp:35:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if (type<=2 && h[i][x]<height)
        ^
ufo.cpp:38:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if (type>=3 && v[i][x]<height)
        ^
ufo.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
ufo.cpp: In function 'int main()':
ufo.cpp:126:12: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ll type;
            ^~~~

• Subtask 1: 5 / 100