Submission #58138

#	Time	Username	Problem	Language	Result	Execution time	Memory
58138		Benq	UFO (IZhO14_ufo)	C++14	100 / 100	1341 ms	163496 KiB

ufo

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

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

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


struct Seg {
    int SZ;
    vi seg;
    
    void init(int _N) {
        SZ = 1; while (SZ < _N) SZ *= 2;
        seg.resize(2*SZ);
    }
    
    int comb(int a, int b) { return max(a,b); } // easily change this to min or max
    
    int fst(int nex, int hei, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R = SZ-1;
        if (seg[ind] < hei || nex > R) return MOD;
        if (L == R) return L;
        
        int M = (L+R)/2;
        if (nex <= M) {
            int x = fst(nex,hei,2*ind,L,M);
            if (x != MOD) return x;
        }
        return fst(nex,hei,2*ind+1,M+1,R);
    }
    
    int lst(int nex, int hei, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R = SZ-1;
        if (seg[ind] < hei || nex < L) return -MOD;
        if (L == R) return L;
        
        int M = (L+R)/2;
        if (nex > M) {
            int x = lst(nex,hei,2*ind+1,M+1,R);
            if (x != -MOD) return x;
        }
        return lst(nex,hei,2*ind,L,M);
    }
    
    void upd(int p, int value) {  // set value at position p
        for (seg[p += SZ] += value; p > 1; p >>= 1)
            seg[p>>1] = comb(seg[p],seg[p^1]); // non-commutative operations
    }
};

int N,M,R,K,P;
vector<Seg> hori, vert;
vector<vi> v;

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> R >> K >> P;
    v.resize(N);
    F0R(i,N) {
        v[i].resize(M);
        F0R(j,M) cin >> v[i][j];
    }
    hori.resize(N), vert.resize(M);
    F0R(i,N) {
        hori[i].init(M);
        F0R(j,M) hori[i].upd(j,v[i][j]);
    }
    F0R(j,M) {
        vert[j].init(N);
        F0R(i,N) {
            vert[j].upd(i,v[i][j]);
            // cout << "OH " << j << " " << i << " " << v[i][j] << "\n";
        }
    }
}

void sub(pi x) {
    v[x.f][x.s] --;
    hori[x.f].upd(x.s,-1);
    vert[x.s].upd(x.f,-1);
}

int main() {
    init();
    F0R(i,K) {
        char c; int pos, hei; cin >> c >> pos >> hei; pos --;
        vpi change;
        if (c == 'N') {
            int nex = 0;
            F0R(i,R) {
                int t = vert[pos].fst(nex,hei);
                if (t == MOD) break;
                change.pb({t,pos});
                nex = t+1;
            }
        } else if (c == 'S') {
            int nex = N-1;
            F0R(i,R) {
                int t = vert[pos].lst(nex,hei);
                if (t == -MOD) break;
                change.pb({t,pos});
                nex = t-1;
            }
        } else if (c == 'W') {
            int nex = 0;
            F0R(i,R) {
                int t = hori[pos].fst(nex,hei);
                if (t == MOD) break;
                change.pb({pos,t});
                nex = t+1;
            }
        } else if (c == 'E') {
            int nex = M-1;
            F0R(i,R) {
                int t = hori[pos].lst(nex,hei);
                if (t == -MOD) break;
                change.pb({pos,t});
                nex = t-1;
            }
        }
        for (auto a: change) sub(a);
    }
    ll cum[sz(v)+1][sz(v[0])+1];
    F0R(i,sz(v)+1) F0R(j,sz(v[0])+1) cum[i][j] = 0;
    F0R(i,sz(v)) F0R(j,sz(v[0])) {
        cum[i+1][j+1] = v[i][j]+cum[i+1][j]+cum[i][j+1]-cum[i][j];
    }
    ll ans = 0;
    F0R(i,sz(v)+1-P) F0R(j,sz(v[0])+1-P) ans = max(ans,cum[i+P][j+P]-cum[i+P][j]-cum[i][j+P]+cum[i][j]);
    /*F0R(i,N) {
        F0R(j,M) cout << v[i][j] << " ";
        cout << "\n";
    }*/
    cout << ans;
    
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 100 / 100