Submission #880276

# Submission time Handle Problem Language Result Execution time Memory
880276 2023-11-29T05:38:31 Z The_Samurai UFO (IZhO14_ufo) C++17
0 / 100
326 ms 88576 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 (tree[x] < v or rx - 1 < i) return -1;
        if (rx - lx == 1) return (tree[x] >= v ? lx : -1);
        int m = (lx + rx) >> 1;
        int ans = get_next(i, v, x << 1, lx, m);
        if (ans != -1) return ans;
        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 (tree[x] < v or i < lx) return -1;
        if (rx - lx == 1) return (tree[x] >= v ? lx : -1);
        int m = (lx + rx) >> 1;
        int ans = get_prev(i, v, x << 1 | 1, m, rx);
        if (ans != -1) return ans;
        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;
            assert(1 <= i and i <= n and v != 0);
            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;
            assert(1 <= j and j <= m and v != 0);
            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);
            }
        }
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) cout << col[i].get(j) << ' ';
//            cout << endl;
//        }
//        cout << endl;
    }
    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()];
      |                            ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 600 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 7 ms 604 KB Output isn't correct
5 Incorrect 31 ms 2140 KB Output isn't correct
6 Incorrect 83 ms 13648 KB Output isn't correct
7 Runtime error 15 ms 16852 KB Execution killed with signal 11
8 Runtime error 13 ms 16852 KB Execution killed with signal 11
9 Runtime error 9 ms 12696 KB Execution killed with signal 11
10 Runtime error 12 ms 16852 KB Execution killed with signal 11
11 Runtime error 15 ms 17752 KB Execution killed with signal 11
12 Runtime error 13 ms 16852 KB Execution killed with signal 11
13 Incorrect 256 ms 35352 KB Output isn't correct
14 Runtime error 14 ms 17792 KB Execution killed with signal 11
15 Runtime error 13 ms 16852 KB Execution killed with signal 11
16 Runtime error 14 ms 17796 KB Execution killed with signal 11
17 Incorrect 326 ms 35660 KB Output isn't correct
18 Incorrect 219 ms 29628 KB Output isn't correct
19 Runtime error 20 ms 25416 KB Execution killed with signal 11
20 Runtime error 78 ms 88576 KB Execution killed with signal 11