Submission #1189727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189727		stefanopulos	UFO (IZhO14_ufo)	C++20	100 / 100	1501 ms	98112 KiB

ufo

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ldb;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;

#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
 
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 200005; 

int n, m, R, K, P;

struct SegTree{

    vector<int> bor;
    void init(int sz){
        bor.resize(4 * sz, 0);
    }

    void update(int v, int tl, int tr, int pos, int val){
        if(tl == tr){
            bor[v] = val;
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid)update(v * 2, tl, mid, pos, val);
        else update(v * 2 + 1, mid + 1, tr, pos, val);
        bor[v] = max(bor[v * 2], bor[v * 2 + 1]);
    }

    pii walkL(int v, int tl, int tr, int l, int r, int h){
        if(tl > tr || l > tr || tl > r)return {-1, -1};
        if(tl >= l && tr <= r){
            if(tl == tr)return (bor[v] >= h ? make_pair(tl, bor[v]) : make_pair(-1, -1));
            int mid = (tl + tr) / 2;
            if(bor[v * 2] >= h)return walkL(v * 2, tl, mid, l, r, h);
            else return walkL(v * 2 + 1, mid + 1, tr, l, r, h);
        }
        int mid = (tl + tr) / 2;

        pii L = walkL(v * 2, tl, mid, l, r, h);
        if(L.fi != -1)return L;

        return walkL(v * 2 + 1, mid + 1, tr, l, r, h);
    }

    pii walkR(int v, int tl, int tr, int l, int r, int h){
        if(tl > tr || l > tr || tl > r)return {-1, -1};
        if(tl >= l && tr <= r){
            if(tl == tr)return (bor[v] >= h ? make_pair(tl, bor[v]) : make_pair(-1, -1));
            int mid = (tl + tr) / 2;
            if(bor[v * 2 + 1] >= h)return walkR(v * 2 + 1, mid + 1, tr, l, r, h);
            else return walkR(v * 2, tl, mid, l, r, h);
        }
        int mid = (tl + tr) / 2;

        pii R = walkR(v * 2 + 1, mid + 1, tr, l, r, h);
        if(R.fi != -1)return R;

        return walkR(v * 2, tl, mid, l, r, h);
    }

    int get(int v, int tl, int tr, int pos){
        if(tl == tr)return bor[v];
        int mid = (tl + tr) / 2;
        if(pos <= mid)return get(v * 2, tl, mid, pos);
        else return get(v * 2 + 1, mid + 1, tr, pos);
    }

};

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> R >> K >> P;
    vector<vector<int>> mat(n, vector<int>(m));
    ff(i,0,n - 1)ff(j,0,m - 1)cin >> mat[i][j];

    vector<SegTree> red(n);
    ff(i,0,n - 1){
        red[i].init(m);
        ff(j,0,m - 1)red[i].update(1,0,m - 1,j,mat[i][j]);
    }

    vector<SegTree> kol(m);
    ff(j,0,m - 1){
        kol[j].init(n);
        ff(i,0,n - 1)kol[j].update(1,0,n - 1,i,mat[i][j]);
    }

    while(K--){
        char t; 
        cin >> t;

        if(t == 'W'){
            int i, h;
            cin >> i >> h; i -= 1;

            int pos = 0;
            for(int _ = 1; _ <= R; _++){
                auto [j, val] = red[i].walkL(1,0,m - 1,pos,m - 1,h);
                if(j == -1)break;

                val -= 1;
                red[i].update(1,0,m - 1,j,val);
                kol[j].update(1,0,n - 1,i,val);
                pos = j + 1;

            }
        
        }

        if(t == 'E'){
            int i, h;
            cin >> i >> h; i--;

            int pos = m - 1;
            for(int _ = 1; _ <= R; _++){
                auto [j, val] = red[i].walkR(1,0,m - 1,0,pos,h);
                if(j == -1)break;

                val -= 1;
                red[i].update(1,0,m - 1,j,val);
                kol[j].update(1,0,n - 1,i,val);
                pos = j - 1;

            }

        }

        if(t == 'N'){
            int j, h;
            cin >> j >> h; j--;

            int pos = 0;
            for(int _ = 1; _ <= R; _++){
                auto [i, val] = kol[j].walkL(1,0,n - 1,pos,n - 1,h);
                if(i == -1)break;

                val -= 1;
                kol[j].update(1,0,n - 1,i,val);
                red[i].update(1,0,m - 1,j,val);
                pos = i + 1;

            }

        }

        if(t == 'S'){
            int j, h;
            cin >> j >> h; j--;
            
            int pos = n - 1;
            for(int _ = 1; _ <= R; _++){
                auto [i, val] = kol[j].walkR(1,0,n - 1,0,pos,h);
                if(i == -1)break;

                val -= 1;
                kol[j].update(1,0,n - 1,i,val);
                red[i].update(1,0,m - 1,j,val);
                pos = i - 1;

            }

        }

    }

    ff(i,0,n - 1)ff(j,0,m - 1)mat[i][j] = red[i].get(1,0,m - 1,j);

    vector<vector<ll>> pref(n + 1, vector<ll>(m + 1, 0));
    ff(i,0,n - 1){
        ff(j,0,m - 1){
            pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + mat[i][j];
        }
    }

    auto query = [&](int x1, int y1, int x2, int y2){
        return pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
    };

    ll rez = 0;
    ff(i,P,n){
        ff(j,P,m){
            ll kol = query(i - P + 1, j - P + 1, i, j);
            rez = max(rez, kol);
        }
    }

    cout << rez << '\n';

    return 0;
}
/*

4 8 2 1 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
E 2 1

4 8 2 3 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
W 2 2
W 2 3
E 2 1

// probati bojenje sahovski
*/
 
 
 
 
 

• Subtask 1: 100 / 100