답안 #90691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90691 2018-12-23T16:18:21 Z popovicirobert UFO (IZhO14_ufo) C++14
45 / 100
778 ms 139500 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, n, 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, n, 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;
}

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Incorrect 2 ms 476 KB Output isn't correct
4 Correct 12 ms 800 KB Output is correct
5 Correct 34 ms 2632 KB Output is correct
6 Correct 203 ms 19784 KB Output is correct
7 Runtime error 271 ms 89936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 239 ms 89936 KB Output is correct
9 Runtime error 301 ms 89936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 248 ms 90064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 238 ms 90064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 249 ms 90296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 592 ms 93404 KB Output is correct
14 Runtime error 254 ms 93404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 271 ms 93404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 264 ms 93404 KB Output is correct
17 Incorrect 778 ms 93404 KB Output isn't correct
18 Correct 253 ms 93404 KB Output is correct
19 Incorrect 266 ms 95596 KB Output isn't correct
20 Correct 316 ms 139500 KB Output is correct