Submission #90693

#	Time	Username	Problem	Language	Result	Execution time	Memory
90693		popovicirobert	UFO (IZhO14_ufo)	C++14	100 / 100	782 ms	94464 KiB

ufo

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

struct SegTree {
    vector <int> aint;
    int n;
    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
    }
    inline void refresh(int nod) {
        aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
    }
    void update(int nod, int left, int right, int pos, int val) {
        if(left == right) {
            aint[nod] = val;
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
            refresh(nod);
        }
    }
    int query_l(int nod, int left, int right, int l, int r, int val) {
        if(l <= left && right <= r) {
            int mid = (left + right) / 2;
            if(aint[nod] < val) {
                return -1;
            }
            if(left == right) {
                return left;
            }
            if(aint[2 * nod] >= val) {
                return query_l(2 * nod, left, mid, l, r, val);
            }
            return query_l(2 * nod + 1, mid + 1, right, l, r, val);
        }
        else {
            int mid = (left + right) / 2;
            int ans = -1;
            if(l <= mid && aint[2 * nod] >= val) {
                ans = query_l(2 * nod, left, mid, l, r, val);
            }
            if(mid < r && ans == -1 && aint[2 * nod + 1] >= val) {
                ans = query_l(2 * nod + 1, mid + 1, right, l, r, val);
            }
            return ans;
        }
    }
    int query_r(int nod, int left, int right, int l, int r, int val) {
        if(l <= left && right <= r) {
            int mid = (left + right) / 2;
            if(aint[nod] < val) {
                return -1;
            }
            if(left == right) {
                return left;
            }
            if(aint[2 * nod + 1] >= val) {
                return query_r(2 * nod + 1, mid + 1, right, l, r, val);
            }
            return query_r(2 * nod, left, mid, l, r, val);
        }
        else {
            int mid = (left + right) / 2;
            int ans = -1;
            if(mid < r && aint[2 * nod + 1] >= val) {
                ans = query_r(2 * nod + 1, mid + 1, right, l, r, val);
            }
            if(l <= mid && ans == -1 && aint[2 * nod] >= val) {
                ans = query_r(2 * nod, left, mid, l, r, val);
            }
            return ans;
        }
    }
};

vector < vector <ll> > mat;
vector < SegTree > row, col;

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, m, r, k, p;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> r >> k >> p;
    mat.resize(n + 1);
    row.resize(n + 1), col.resize(m + 1);
    for(i = 1; i <= n; i++) {
        row[i].init(m);
    }
    for(i = 1; i <= m; i++) {
        col[i].init(n);
    }
    mat[0].resize(m + 1);
    for(i = 1; i <= n; i++) {
        mat[i].resize(m + 1);
        for(j = 1; j <= m; j++) {
            cin >> mat[i][j];
            row[i].update(1, 1, m, j, mat[i][j]);
            col[j].update(1, 1, n, i, mat[i][j]);
        }
    }
    while(k > 0) {
        k--;
        int id, h;
        char ch;
        cin >> ch >> id >> h;
        if(ch == 'N') {
            int pos = 0;
            i = 0;
            while(i < r && pos < n) {
                pos = col[id].query_l(1, 1, n, pos + 1, n, h);
                if(pos == -1) {
                    break;
                }
                mat[pos][id]--;
                col[id].update(1, 1, n, pos, mat[pos][id]);
                i++;
            }
        }
        if(ch == 'S') {
            int pos = n + 1;
            i = 0;
            while(i < r && pos > 1) {
                pos = col[id].query_r(1, 1, n, 1, pos - 1, h);
                if(pos == -1) {
                    break;
                }
                mat[pos][id]--;
                col[id].update(1, 1, n, pos, mat[pos][id]);
                i++;
            }
        }
        if(ch == 'W') {
            int pos = 0;
            i = 0;
            while(i < r && pos < m) {
                pos = row[id].query_l(1, 1, m, pos + 1, m, h);
                if(pos == -1) {
                    break;
                }
                mat[id][pos]--;
                row[id].update(1, 1, m, pos, mat[id][pos]);
                i++;
            }
        }
        if(ch == 'E') {
            int pos = m + 1;
            i = 0;
            while(i < r && pos > 1) {
                pos = row[id].query_r(1, 1, m, 1, pos - 1, h);
                if(pos == -1) {
                    break;
                }
                mat[id][pos]--;
                row[id].update(1, 1, m, pos, mat[id][pos]);
                i++;
            }
        }
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
        }
    }
    ll ans = 0;
    for(i = p; i <= n; i++) {
        for(j = p; j <= m; j++) {
            ans = max(ans, mat[i][j] - mat[i - p][j] - mat[i][j - p] + mat[i - p][j - p]);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100