Submission #171764

#	Time	Username	Problem	Language	Result	Execution time	Memory
171764		VEGAnn	UFO (IZhO14_ufo)	C++14	100 / 100	1085 ms	123512 KiB

ufo

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 1000100;
const int K = 110;
const int PW = 20;
vector<vector<int> > a, pref;
int n, m, R, k, p, pos;
bool fd;
int ans = 0;

struct seg_tree{
    vector<int> mx;
    int tp, nm;

    seg_tree(): mx(0), tp(-1), nm(-1) {}

    seg_tree(int _tp, int _nm): mx(0), tp(_tp), nm(_nm) {
        if (tp == 0){
            mx.resize(4 * m);
            build(1, 0, m - 1);
        } else {
            mx.resize(4 * n);
            build(1, 0, n - 1);
        }
    }

    void build(int v, int l, int r){
        if (l == r){
            if (tp == 0)
                mx[v] = a[nm][l];
            else mx[v] = a[l][nm];
            return;
        }
        int md = (l + r) >> 1;
        build(v + v, l, md);
        build(v + v + 1, md + 1, r);
        mx[v] = max(mx[v + v], mx[v + v + 1]);
    }

    void real_search_rgt(int v, int l, int r, int vl){
        if (l == r){
            fd = 1;
            pos = l;
            return;
        }
        int md = (l + r) >> 1;
        if (mx[v + v + 1] >= vl)
            real_search_rgt(v + v + 1, md + 1, r, vl);
        else real_search_rgt(v + v, l, md, vl);
    }

    void search_rgt(int v, int tl, int tr, int l, int r, int vl){
        if (l > r || fd) return;
        if (tl == l && tr == r){
            if (mx[v] >= vl)
                real_search_rgt(v, l, r, vl);
            return;
        }
        int md = (tl + tr) >> 1;
        search_rgt(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
        search_rgt(v + v, tl, md, l, min(r, md), vl);
    }

    void real_search_lft(int v, int l, int r, int vl){
        if (l == r){
            fd = 1;
            pos = l;
            return;
        }
        int md = (l + r) >> 1;
        if (mx[v + v] >= vl)
            real_search_lft(v + v, l, md, vl);
        else real_search_lft(v + v + 1, md + 1, r, vl);
    }

    void search_lft(int v, int tl, int tr, int l, int r, int vl){
        if (l > r || fd) return;
        if (tl == l && tr == r){
            if (mx[v] >= vl)
                real_search_lft(v, l, r, vl);
            return;
        }
        int md = (tl + tr) >> 1;
        search_lft(v + v, tl, md, l, min(r, md), vl);
        search_lft(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
    }

    void update(int v, int l, int r, int ps){
        if (l == r){
            if (tp == 0)
                mx[v] = a[nm][l];
            else mx[v] = a[l][nm];
            return;
        }
        int md = (l + r) >> 1;
        if (ps <= md)
            update(v + v, l, md, ps);
        else update(v + v + 1, md + 1, r, ps);
        mx[v] = max(mx[v + v], mx[v + v + 1]);
    }

};
seg_tree row[N], col[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m >> R >> k >> p;

    a.resize(n);
    for (int i = 0; i < n; i++){
        a[i].resize(m);
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }

    for (int i = 0; i < n; i++)
        row[i] = seg_tree(0, i);

    for (int i = 0; i < m; i++)
        col[i] = seg_tree(1, i);

    for (; k; k--){
        char tp; int nm, ht;
        cin >> tp >> nm >> ht;
        nm--;
        if (tp == 'N'){
            int pr = -1;
            for (int it = 0; it < R; it++){
                fd = 0;
                pos = -1;
                col[nm].search_lft(1, 0, n - 1, pr + 1, n - 1, ht);
                if (!fd) break;
                pr = pos;
                a[pos][nm]--;
                col[nm].update(1, 0, n - 1, pos);
                row[pos].update(1, 0, m - 1, nm);
            }
        } else if (tp == 'S'){
            int pr = n;
            for (int it = 0; it < R; it++){
                fd = 0;
                pos = -1;
                col[nm].search_rgt(1, 0, n - 1, 0, pr - 1, ht);
                if (!fd) break;
                pr = pos;
                a[pos][nm]--;
                col[nm].update(1, 0, n - 1, pos);
                row[pos].update(1, 0, m - 1, nm);
            }
        } else if (tp == 'W'){
            int pr = -1;
            for (int it = 0; it < R; it++){
                fd = 0;
                pos = -1;
                row[nm].search_lft(1, 0, m - 1, pr + 1, m - 1, ht);
                if (!fd) break;
                pr = pos;
                a[nm][pos]--;
                row[nm].update(1, 0, m - 1, pos);
                col[pos].update(1, 0, n - 1, nm);
            }
        } else {
            int pr = m;
            for (int it = 0; it < R; it++){
                fd = 0;
                pos = -1;
                row[nm].search_rgt(1, 0, m - 1, 0, pr - 1, ht);
                if (!fd) break;
                pr = pos;
                a[nm][pos]--;
                row[nm].update(1, 0, m - 1, pos);
                col[pos].update(1, 0, n - 1, nm);
            }
        }
    }

    pref.resize(n + 1);
    for (int i = 0; i <= n; i++)
        pref[i].resize(m + 1);

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
        pref[i][j] = a[i - 1][j - 1] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
    }

    for (int i = p; i <= n; i++)
    for (int j = p; j <= m; j++){
        int res = pref[i][j] - pref[i - p][j] - pref[i][j - p] + pref[i - p][j - p];
        ans = max(ans, res);
    }

    cout << ans;

    return 0;
}

• Subtask 1: 100 / 100