Submission #655593

#	Time	Username	Problem	Language	Result	Execution time	Memory
655593		KiriLL1ca	UFO (IZhO14_ufo)	C++17	100 / 100	854 ms	98724 KiB

ufo

#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;
}

• Subtask 1: 100 / 100