답안 #655593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655593 2022-11-04T19:39:09 Z KiriLL1ca UFO (IZhO14_ufo) C++17
100 / 100
854 ms 98724 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef unsigned int uint;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

struct segtree {
        int n; vector <int> t;
        segtree (int n = 0) : n(n), t(4 * n) {}
        inline void upd (int v, int tl, int tr, int pos, int x) {
                if (tl == tr) return void(t[v] = x);
                int tm = (tl + tr) >> 1;
                if (pos <= tm) upd(v << 1, tl, tm, pos, x);
                else upd(v << 1 | 1, tm + 1, tr, pos, x);
                t[v] = max(t[v << 1], t[v << 1 | 1]);
        }
        inline int lef (int v, int tl, int tr, int i, int x) {
                if (t[v] < x || tr < i) return -1;
                if (tl == tr) return tl;
                int tm = (tl + tr) >> 1;
                int a = lef(v << 1, tl, tm, i, x);
                if (!~a) return lef(v << 1 | 1, tm + 1, tr, i, x);
                return a;
        }
        inline int rig (int v, int tl, int tr, int i, int x) {
                if (t[v] < x || tl > i) return -1;
                if (tl == tr) return tl;
                int tm = (tl + tr) >> 1;
                int a = rig(v << 1 | 1, tm + 1, tr, i, x);
                if (!~a) return rig(v << 1, tl, tm, i, x);
                return a;
        }

        inline void upd (int pos, int x) { upd(1, 0, n - 1, pos, x); }
        inline int lef (int i, int x) { return lef(1, 0, n - 1, i, x); }
        inline int rig (int i, int x) { return rig(1, 0, n - 1, i, x); }
};

inline void solve () {
        int n, m, r, q, p; cin >> n >> m >> r >> q >> p;
        vector <segtree> row (n, segtree (m)), col (m, segtree (n));
        vector <vector <ll>> a (n, vector <ll> (m));
        for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                        cin >> a[i][j];
                        row[i].upd(j, a[i][j]);
                        col[j].upd(i, a[i][j]);
                }
        }
        while (q--) {
                char c; int id, x; cin >> c >> id >> x; --id;
                if (c == 'N') {
                        int cur = 0;
                        for (int it = 0; it < r; ++it) {
                                int pos = col[id].lef(cur, x);
                                if (!~pos) break;
                                --a[pos][id];
                                col[id].upd(pos, a[pos][id]);
                                row[pos].upd(id, a[pos][id]);
                                cur = pos + 1;
                        }
                }
                else if (c == 'S') {
                        int cur = n - 1;
                        for (int it = 0; it < r; ++it) {
                                int pos = col[id].rig(cur, x);
                                if (!~pos) break;
                                --a[pos][id];
                                col[id].upd(pos, a[pos][id]);
                                row[pos].upd(id, a[pos][id]);
                                cur = pos - 1;
                        }
                }
                else if (c == 'W') {
                        int cur = 0;
                        for (int it = 0; it < r; ++it) {
                                int pos = row[id].lef(cur, x);
                                if (!~pos) break;
                                --a[id][pos];
                                row[id].upd(pos, a[id][pos]);
                                col[pos].upd(id, a[id][pos]);
                                cur = pos + 1;
                        }
                }
                else if (c == 'E') {
                        int cur = m - 1;
                        for (int it = 0; it < r; ++it) {
                                int pos = row[id].rig(cur, x);
                                if (!~pos) break;
                                --a[id][pos];
                                row[id].upd(pos, a[id][pos]);
                                col[pos].upd(id, a[id][pos]);
                                cur = pos - 1;
                        }
                }
        }
        for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                        if (i) a[i][j] += a[i - 1][j];
                        if (j) a[i][j] += a[i][j - 1];
                        if (i && j) a[i][j] -= a[i - 1][j - 1];
                }
        }
        auto get = [&] (int i, int j, int ii, int jj) { return a[ii][jj] - (i ? a[i - 1][jj] : 0) - (j ? a[ii][j - 1] : 0) + (i && j ? a[i - 1][j - 1] : 0); };

        ll ans = 0;
        for (int i = 0; i + p - 1 < n; ++i) {
                for (int j = 0; j + p - 1 < m; ++j) {
                        umax(ans, get(i, j, i + p - 1, j + p - 1));
                }
        }
        cout << ans << endl;
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 852 KB Output is correct
5 Correct 71 ms 3188 KB Output is correct
6 Correct 179 ms 22892 KB Output is correct
7 Correct 265 ms 52764 KB Output is correct
8 Correct 197 ms 49292 KB Output is correct
9 Correct 457 ms 45704 KB Output is correct
10 Correct 497 ms 48520 KB Output is correct
11 Correct 353 ms 47656 KB Output is correct
12 Correct 520 ms 48396 KB Output is correct
13 Correct 610 ms 52552 KB Output is correct
14 Correct 443 ms 47732 KB Output is correct
15 Correct 596 ms 49932 KB Output is correct
16 Correct 214 ms 49840 KB Output is correct
17 Correct 845 ms 56920 KB Output is correct
18 Correct 233 ms 47976 KB Output is correct
19 Correct 326 ms 55432 KB Output is correct
20 Correct 854 ms 98724 KB Output is correct