Submission #343822

#	Time	Username	Problem	Language	Result	Execution time	Memory
343822		apostoldaniel854	UFO (IZhO14_ufo)	C++14	45 / 100	976 ms	165628 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 3e4;

struct BestSegTree {
    vector <int> seg;
    int n;
    void init (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
    }
    void update (int node, int lb, int rb, int pos, int to_add) {
        if (lb == rb) {
            seg[node] += to_add;
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (pos <= mid)
            update (left_node, lb, mid, pos, to_add);
        else
            update (right_node, mid + 1, rb, pos, to_add);
        seg[node] = max (seg[left_node], seg[right_node]);
    }
    int query (int node, int lb, int rb, int bound) {
        if (lb == rb)
            return lb;
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (seg[left_node] >= bound)
            return query (left_node, lb, mid, bound);
        if (seg[right_node] >= bound)
            return query (left_node, mid + 1, rb, bound);
        return -1;
    }
    int queryPos (int node, int lb, int rb, int pos) {
        if (lb == rb)
            return seg[node];
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (pos <= mid)
            return queryPos (left_node, lb, mid, pos);
        else
            return queryPos (right_node, mid + 1, rb, pos);
    }
};
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, m, r, k, p;
    cin >> n >> m >> r >> k >> p;
    vector <BestSegTree> segW (n + 1), segE (n + 1);
    for (int i = 1; i <= n; i++)
        segW[i].init (m), segE[i].init (m);
    vector <BestSegTree> segS (m + 1), segN (m + 1);
    for (int i = 1; i <= m; i++)
        segS[i].init (n), segN[i].init (n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            segS[j].update (1, 1, n, i, x);
            segN[j].update (1, 1, n, n - i + 1, x);
            segW[i].update (1, 1, m, j, x);
            segE[i].update (1, 1, m, m - j + 1, x);
        }
    }
    while (k--) {
        char dir;
        cin >> dir;
        if (dir == 'W') {
            int row, height;
            cin >> row >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int col = segW[row].query (1, 1, m, height);
                if (col == -1)
                    good = false;
                else {
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
        if (dir == 'E') {
            int row, height;
            cin >> row >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int col = segE[row].query (1, 1, m, height);
                if (col == -1)
                    good = false;
                else {
                    col = m - col + 1;
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
        if (dir == 'S') {
            int col, height;
            cin >> col >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int row = segS[col].query (1, 1, n, height);
                if (row == -1)
                    good = false;
                else {
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
        if (dir == 'N') {
            int col, height;
            cin >> col >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int row = segN[col].query (1, 1, n, height);
                if (row == -1)
                    good = false;
                else {
                    row = n - row + 1;
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
    }
    vector <vector <int>> a (n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].resize (m + 1);
        for (int j = 1; j <= m; j++)
            a[i][j] = segW[i].queryPos (1, 1, m, j);
    }
    int mx = 0;
    for (int i = 1; i <= n - p + 1; i++)
        for (int j = 1; j <= m - p + 1; j++) {
            int cnt = 0;
            for (int x = i; x < i + p; x++)
                for (int y = j; y < j + p; y++)
                    cnt += a[x][y];
            mx = max (mx, cnt);
        }
    cout << mx << "\n";
    return 0;
}

• Subtask 1: 45 / 100