Submission #171965

#	Time	Username	Problem	Language	Result	Execution time	Memory
171965		DeD_TihoN	UFO (IZhO14_ufo)	C++14	100 / 100	1807 ms	166388 KiB

ufo

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define endl '\n'
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=2e6+7;
const int inf=1e18+5;
const int mod=1e9+7;
const ld eps=1e-9;

vector< vector<int> >t[2];

void update(int type,int num,int v,int l,int r,int pos,int x)
{
    if (l==r){
        t[type][num][v]=x;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        update(type,num,v+v,l,mid,pos,x);
    }
    else {
        update(type,num,v+v+1,mid+1,r,pos,x);
    }
    t[type][num][v]=max(t[type][num][v+v],t[type][num][v+v+1]);
}

int get(int type,int num,int v,int l,int r,int l1,int r1,int x,bool left1)
{
    if (l>r1 || r<l1)return -1;
    if (t[type][num][v]<x)return -1;
    if (l==r){
        return l;
    }
    int mid=(l+r)/2;
    if (left1){
        int f=get(type,num,v+v,l,mid,l1,r1,x,left1);
        if (f!=-1)return f;
        return get(type,num,v+v+1,mid+1,r,l1,r1,x,left1);
    }
    else {
        int f=get(type,num,v+v+1,mid+1,r,l1,r1,x,left1);
        if (f!=-1)return f;
        return get(type,num,v+v,l,mid,l1,r1,x,left1);
    }
}

main ()
{
    ios
    int n,m,r,k,p;
    cin>>n>>m>>r>>k>>p;
    int a[n+1][m+1];
    ll pref[n+1][m+1];
    for (int i=0;i<=n;++i){
        vector<int>b;
        for (int j=0;j<=m;++j){
            a[i][j]=0;
            pref[i][j]=0;
        }
        for (int j=0;j<=4*m;++j){
            b.pb((int)0);
        }
        t[0].pb(b);
    }
    for (int j=0;j<=m;++j){
        vector<int>b;
        for (int i=0;i<=4*n;++i){
            b.pb((int)0);
        }
        t[1].pb(b);
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            cin>>a[i][j];
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            update(0,i,1,1,m,j,a[i][j]);
            update(1,j,1,1,n,i,a[i][j]);
        }
    }
    for (int t=1;t<=k;++t){
        char ch;
        cin>>ch;
        int i,h;
        cin>>i>>h;
        if (ch=='N'){
            int l1=1;
            int r1=n;
            for (int kol=1;kol<=r && l1<=r1;++kol){
                int pos=get(1,i,1,1,n,l1,r1,h,1);
                if (pos==-1)break;
                --a[pos][i];
                update(1,i,1,1,n,pos,a[pos][i]);
                update(0,pos,1,1,m,i,a[pos][i]);
                l1=pos+1;
            }
        }
        if (ch=='E'){
            int l1=1;
            int r1=m;
            for (int kol=1;kol<=r && l1<=r1;++kol){
                int pos=get(0,i,1,1,m,l1,r1,h,0);
                if (pos==-1)break;
                --a[i][pos];
                update(0,i,1,1,m,pos,a[i][pos]);
                update(1,pos,1,1,n,i,a[i][pos]);
                r1=pos-1;
            }
        }
        if (ch=='S'){
            int l1=1;
            int r1=n;
            for (int kol=1;kol<=r && l1<=r1;++kol){
                int pos=get(1,i,1,1,n,l1,r1,h,0);
                if (pos==-1)break;
                --a[pos][i];
                update(1,i,1,1,n,pos,a[pos][i]);
                update(0,pos,1,1,m,i,a[pos][i]);
                r1=pos-1;
            }
        }
        if (ch=='W'){
            int l1=1;
            int r1=m;
            for (int kol=1;kol<=r && l1<=r1;++kol){
                int pos=get(0,i,1,1,m,l1,r1,h,1);
                if (pos==-1)break;
                --a[i][pos];
                update(0,i,1,1,m,pos,a[i][pos]);
                update(1,pos,1,1,n,i,a[i][pos]);
                l1=pos+1;
            }
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
        }
    }
    ll ans=0;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            if (i>=p && j>=p){
                ans=max(ans,pref[i][j]-pref[i][j-p]-pref[i-p][j]+pref[i-p][j-p]);
            }
        }
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

ufo.cpp:76:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

• Subtask 1: 100 / 100