Submission #90692

# Submission time Handle Problem Language Result Execution time Memory
90692 2018-12-23T16:19:39 Z popovicirobert UFO (IZhO14_ufo) C++14
65 / 100
846 ms 137012 KB
#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, n, 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, n, 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;
}

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Incorrect 2 ms 544 KB Output isn't correct
4 Correct 11 ms 796 KB Output is correct
5 Correct 45 ms 2592 KB Output is correct
6 Correct 192 ms 19684 KB Output is correct
7 Correct 275 ms 47316 KB Output is correct
8 Correct 251 ms 47396 KB Output is correct
9 Incorrect 413 ms 47396 KB Output isn't correct
10 Correct 434 ms 50064 KB Output is correct
11 Incorrect 401 ms 50680 KB Output isn't correct
12 Correct 419 ms 52492 KB Output is correct
13 Runtime error 640 ms 72528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 392 ms 85416 KB Output is correct
15 Incorrect 476 ms 87708 KB Output isn't correct
16 Correct 255 ms 87708 KB Output is correct
17 Runtime error 846 ms 90860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Correct 251 ms 90860 KB Output is correct
19 Incorrect 276 ms 93240 KB Output isn't correct
20 Correct 294 ms 137012 KB Output is correct