oj.uz

Submission #171965

# Submission time Handle Problem Language Result Execution time Memory
171965 2019-12-30T17:15:29 Z DeD_TihoN UFO (IZhO14_ufo) C++14
100 / 100
 1807 ms 166388 KB 
#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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 23 ms 1272 KB Output is correct
5 Correct 120 ms 5492 KB Output is correct
6 Correct 384 ms 41080 KB Output is correct
7 Correct 543 ms 90424 KB Output is correct
8 Correct 493 ms 89380 KB Output is correct
9 Correct 888 ms 83912 KB Output is correct
10 Correct 1008 ms 89292 KB Output is correct
11 Correct 719 ms 88032 KB Output is correct
12 Correct 978 ms 89372 KB Output is correct
13 Correct 1109 ms 93496 KB Output is correct
14 Correct 923 ms 87936 KB Output is correct
15 Correct 1056 ms 89348 KB Output is correct
16 Correct 474 ms 87740 KB Output is correct
17 Correct 1494 ms 94800 KB Output is correct
18 Correct 406 ms 82400 KB Output is correct
19 Correct 644 ms 97844 KB Output is correct
20 Correct 1807 ms 166388 KB Output is correct