답안 #880273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880273 2023-11-29T05:17:50 Z The_Samurai UFO (IZhO14_ufo) C++17
0 / 100
334 ms 88684 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;
            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);
            }
        }
//        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()];
      |                            ~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 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 6 ms 712 KB Output isn't correct
5 Incorrect 30 ms 2140 KB Output isn't correct
6 Incorrect 81 ms 13660 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 13 ms 16932 KB Execution killed with signal 11
11 Runtime error 14 ms 17900 KB Execution killed with signal 11
12 Runtime error 14 ms 16860 KB Execution killed with signal 11
13 Incorrect 261 ms 35196 KB Output isn't correct
14 Runtime error 14 ms 17796 KB Execution killed with signal 11
15 Runtime error 13 ms 16832 KB Execution killed with signal 11
16 Runtime error 14 ms 17796 KB Execution killed with signal 11
17 Incorrect 334 ms 35412 KB Output isn't correct
18 Incorrect 221 ms 29528 KB Output isn't correct
19 Runtime error 22 ms 25408 KB Execution killed with signal 11
20 Runtime error 79 ms 88684 KB Execution killed with signal 11