답안 #917471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917471 2024-01-28T09:05:55 Z atom UFO (IZhO14_ufo) C++17
45 / 100
1902 ms 243076 KB
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

template <typename T>
struct SegmentTree {
    vector <T> f, a;
    int n;
    T NEUTRAL = numeric_limits <T> :: min();
    SegmentTree (int _n = 0) { init(_n); }
    void init(int _n) {
        n = _n;
        f.assign((n << 1) + 5, NEUTRAL);
        a.resize(n + 5);
    }
    T merge(T x, T y) { return max(x, y); }
    void build() {
        for (int x = 1; x <= n; ++x) f[x + n] = a[x];
        for (int x = n; x >= 1; --x)
            f[x] = merge(f[x << 1], f[x << 1 | 1]);
    }
    void upd(int p, int val) {
        f[p += n] += val;
        for (; p > 0; p >>= 1)
            f[p >> 1] = merge(f[p], f[p ^ 1]);
    }
    T qry(int p) { return f[p + n]; }
    T qry(int l, int r) {
        T ql = NEUTRAL;
        T qr = NEUTRAL;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ql = merge(ql, f[l++]);
            if (r & 1) qr = merge(f[--r], qr);
        }
        return merge(ql, qr);
    }
    // t = 0, find first element >= x to the left, t = 1 ..to the right
    T get(int p, int x, int t) {
        int l = (t? p : 1);
        int r = (t? n : p);
        int ans = -1;
        while (l <= r) {
            int m = (l + r) >> 1;
            if ((t? qry(l, m) : qry(m, r)) >= x) {
                ans = m;
                t? (r = m - 1) : l = (m + 1);
            }
            else t? (l = m + 1) : (r = m - 1);
        }
        return ans;
    }
};

int n, m, rd, k, p;
vector <vector <int>> sh;
vector <SegmentTree <int>> col, row;

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

    cin >> n >> m >> rd >> k >> p;
    sh.assign(n + 5, vector <int> (m + 5, 0));
    row.resize(n + 5);
    col.resize(m + 5);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> sh[i][j];
    for (int i = 1; i <= n; ++i) {
        row[i].init(m);
        for (int j = 1; j <= m; ++j) row[i].a[j] = sh[i][j];
        row[i].build();
    }
    for (int i = 1; i <= m; ++i) {
        col[i].init(n);
        for (int j = 1; j <= n; ++j) col[i].a[j] = sh[j][i];
        col[i].build();
    }
    // rd <= 10? -> Q*10*log(N);
    for (int _i = 1; _i <= k; ++_i) {
        char cmd; int x, h;
        cin >> cmd >> x >> h;
        int cnt = rd;
        if (cmd == 'N' || cmd == 'S') {
            int t = (cmd == 'N');
            int pos = (cmd == 'N'? 1 : n);
            int y = col[x].get(pos, h, t);
            while (y != -1 && cnt > 0) {
                col[x].upd(y, -1);
                row[y].upd(x, -1);
                y = col[x].get(y + (cmd == 'N'? 1 : -1), h, t);
                --cnt;
            }
        }
        else {
            int t = (cmd == 'W');
            int pos = (cmd == 'W'? 1 : m);
            int y = row[x].get(pos, h, t);
            while (y != -1 && cnt > 0) {
                row[x].upd(y, -1);
                col[y].upd(x, -1);
                y = row[x].get(y + (cmd == 'W'? 1 : -1), h, t);
                --cnt;
            }
        }

    }

    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 1; j <= m; ++j) {
    //         sh[i][j] = col[j].qry(i);
    //         cout << sh[i][j] << " \n"[j == m];
    //     }
    // }
    vector <vector <ll>> prf(n + 5, vector <ll> (m + 5, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            prf[i][j] = prf[i - 1][j] + prf[i][j - 1] - prf[i - 1][j - 1] + sh[i][j]; 
    auto qry = [&] (int x, int y, int X, int Y) {
        return prf[X][Y] + prf[x - 1][y - 1] - prf[X][y - 1] - prf[x - 1][Y];
    };

    ll ans = 0;
    for (int r = 1; r + p - 1 <= n; ++r) {
        for (int c = 1; c + p - 1 <= m; ++c) {
            int R = r + p - 1; int C = c + p - 1;
            ll sum = qry(r, c, R, C);
            if (ans < sum) {
                // debug(r, c, R, C);
                ans = sum;
            }
        }
    }
    cout << ans << "\n";
}


# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 572 KB Output isn't correct
4 Incorrect 10 ms 860 KB Output isn't correct
5 Incorrect 75 ms 3668 KB Output isn't correct
6 Incorrect 128 ms 19540 KB Output isn't correct
7 Incorrect 226 ms 59676 KB Output isn't correct
8 Correct 193 ms 58008 KB Output is correct
9 Incorrect 697 ms 47376 KB Output isn't correct
10 Correct 1080 ms 57524 KB Output is correct
11 Incorrect 726 ms 58744 KB Output isn't correct
12 Correct 1200 ms 57256 KB Output is correct
13 Correct 1269 ms 65144 KB Output is correct
14 Correct 750 ms 58748 KB Output is correct
15 Incorrect 1228 ms 58388 KB Output isn't correct
16 Correct 242 ms 60604 KB Output is correct
17 Incorrect 1902 ms 67592 KB Output isn't correct
18 Correct 241 ms 66156 KB Output is correct
19 Incorrect 553 ms 77336 KB Output isn't correct
20 Correct 1012 ms 243076 KB Output is correct