Submission #880255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880255	2023-11-29T04:51:41 Z	The_Samurai	UFO (IZhO14_ufo)	C++17	0 / 100	272 ms	90588 KB

// I stand with PALESTINE




//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

struct segtree {
    vector<int> tree;
    int size;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, 0);
    }

    void build(vector<int> &a) {
        init((int) a.size());
        for (int p = size; p < size + a.size(); p++) tree[p] = a[p - (int) a.size()];
        for (int p = size - 1; p > 0; p--) tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
    }

    void upd(int p, int v) {
        p += size;
        tree[p] = v;
        for (; p > 1; p >>= 1) tree[p >> 1] = max(tree[p], tree[p ^ 1]);
    }

    int get_next(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) return (tree[x] >= v ? lx : -1);
        int m = (lx + rx) >> 1;
        if (lx >= i and tree[x << 1] >= v) return get_next(i, v, x << 1, lx, m);
        return get_next(i, v, x << 1 | 1, m, rx);
    }

    int get_next(int i, int v) {
        return get_next(i, v, 1, 0, size);
    }

    int get_prev(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) return (tree[x] >= v ? lx : -1);
        int m = (lx + rx) >> 1;
        if (m <= i and tree[x << 1 | 1] >= v) return get_prev(i, v, x << 1 | 1, m, rx);
        return get_prev(i, v, x << 1, lx, m);
    }

    int get_prev(int i, int v) {
        return get_prev(i, v, 1, 0, size);
    }

    int get(int p) {
        return tree[p + size];
    }
};

void solve() {
    int n, m, r, q, p;
    cin >> n >> m >> r >> q >> p;
    vector<segtree> col(n), row(m);
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> a[i][j];
        col[i].build(a[i]);
    }
    vector<int> copy_row(n);
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) copy_row[i] = a[i][j];
        row[j].build(copy_row);
    }
    while (q--) {
        char op;
        cin >> op;
        if (op == 'W' or op == 'E') {
            int i, v;
            cin >> i >> v;
            i--;
            int now, cnt = 0;
            if (op == 'W') now = col[i].get_next(0, v);
            else now = col[i].get_prev(m, v);
            while (cnt < r and now != -1) {
                row[now].upd(i, col[i].get(now) - 1);
                col[i].upd(now, col[i].get(now) - 1);
                cnt++;
                if (op == 'W') now = col[i].get_next(now + 1, v);
                else now = col[i].get_prev(now - 1, v);
            }
        } else {
            int j, v;
            cin >> j >> v;
            j--;
            int now, cnt = 0;
            if (op == 'N') now = row[j].get_next(0, v);
            else now = row[j].get_prev(n, v);
            while (cnt < r and now != -1) {
                col[now].upd(j, row[j].get(now) - 1);
                row[j].upd(now, row[j].get(now) - 1);
                cnt++;
                if (op == 'N') now = row[j].get_next(now + 1, v);
                else now = row[j].get_prev(now - 1, v);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= n - p; i++) {
        for (int j = 0; j <= m - p; j++) {
            int sum = 0;
            for (int x = i; x < i + p; x++) {
                for (int y = j; y < j + p; y++) {
                    sum += col[x].get(y);
                }
            }
            ans = max(ans, sum);
        }
    }
    cout << ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Compilation message

ufo.cpp: In member function 'void segtree::build(std::vector<int>&)':
ufo.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int p = size; p < size + a.size(); p++) tree[p] = a[p - (int) a.size()];
      |                            ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Output isn't correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	1 ms	348 KB	Output isn't correct
4	Incorrect	4 ms	604 KB	Output isn't correct
5	Incorrect	15 ms	2772 KB	Output isn't correct
6	Incorrect	63 ms	16720 KB	Output isn't correct
7	Runtime error	17 ms	17636 KB	Execution killed with signal 11
8	Runtime error	14 ms	17364 KB	Execution killed with signal 11
9	Runtime error	9 ms	12952 KB	Execution killed with signal 11
10	Runtime error	13 ms	17172 KB	Execution killed with signal 11
11	Runtime error	19 ms	18300 KB	Execution killed with signal 11
12	Runtime error	13 ms	17360 KB	Execution killed with signal 11
13	Incorrect	216 ms	39760 KB	Output isn't correct
14	Runtime error	17 ms	18428 KB	Execution killed with signal 11
15	Runtime error	13 ms	17364 KB	Execution killed with signal 11
16	Runtime error	14 ms	18304 KB	Execution killed with signal 11
17	Incorrect	272 ms	44232 KB	Output isn't correct
18	Incorrect	196 ms	35152 KB	Output isn't correct
19	Runtime error	20 ms	25928 KB	Execution killed with signal 11
20	Runtime error	78 ms	90588 KB	Execution killed with signal 11

Submission #880255

Compilation message

Subtask #1 0 / 100.0

Subtask #1
0 / 100.0