답안 #102581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102581	2019-03-26T02:59:56 Z	nickyrio	UFO (IZhO14_ufo)	C++17	100 / 100	1501 ms	153848 KB

ufo

//
//  main.cpp
//  UFO
//
//  Created by Nguyen E Ro on 3/26/19.
//  Copyright © 2019 Nguyen E Ro. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

int n, m, r, k, p;
vector< vector<int> > a;

vector<int> temp;
int remain;

struct SegmentTreeMax {
    vector<int> Max;
    int n;
    
    SegmentTreeMax(int n):n(n), Max(n * 4 + 10) {}
    SegmentTreeMax() {}
    
    void Reset(int n) {
        this -> n = n;
        Max.resize(n * 4 + 10);
    }
    
    void Update(int u, int val) { Update(1, 1, n, u, val); }
    
    void FindFirst(int k) {
        FindFirst(1, 1, n, k);
    }
    
    void FindLast(int k) {
        FindLast(1, 1, n, k);
    }

private:
    void Update(int k, int l, int r, int u, int val) {
        if (l == r) {
            Max[k] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (u <= m) Update(k << 1, l, m, u, val);
        else Update(k << 1 | 1, m + 1, r, u, val);
        Max[k] = max(Max[k << 1], Max[k << 1 | 1]);
    }
    
    void FindFirst(int k, int l, int r, int x) {
        if (remain == 0 || Max[k] < x) return;
        if (l == r) {
            --remain;
            temp.push_back(l);
            return;
        }
        int m = (l + r) >> 1;
        FindFirst(k << 1, l, m, x);
        FindFirst(k << 1 | 1, m + 1, r, x);
    }
    
    void FindLast(int k, int l, int r, int x) {
        if (remain == 0 || Max[k] < x) return;
        if (l == r) {
            --remain;
            temp.push_back(l);
            return;
        }
        int m = (l + r) >> 1;
        FindLast(k << 1 | 1, m + 1, r, x);
        FindLast(k << 1, l, m, x);
    }
};

SegmentTreeMax Row[N], Col[N];

int main() {
    cin >> m >> n >> r >> k >> p;
    a.resize(m + 1);
    for (int i = 1; i <= n; ++i) {
        Col[i].Reset(m);
    }
    a[0].resize(n + 1);
    for (int i = 1; i <= m; ++i) {
        Row[i].Reset(n);
        a[i].resize(n + 1);
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
            Row[i].Update(j, a[i][j]);
            Col[j].Update(i, a[i][j]);
        }
    }
    for (int i = 0; i < k; ++i) {
        char type;
        int id, h;
        cin >> type >> id >> h;
        temp.clear();
        remain = r;
        if (type == 'W') {
            Row[id].FindFirst(h);
            for (int x : temp) {
                --a[id][x];
                Row[id].Update(x, a[id][x]);
                Col[x].Update(id, a[id][x]);
            }
        }
        if (type == 'E') {
            Row[id].FindLast(h);
            for (int x : temp) {
                --a[id][x];
                Row[id].Update(x, a[id][x]);
                Col[x].Update(id, a[id][x]);
            }
        }
        if (type == 'N') {
            Col[id].FindFirst(h);
            for (int x : temp) {
                --a[x][id];
                Row[x].Update(id, a[x][id]);
                Col[id].Update(x, a[x][id]);
            }
        }
        if (type == 'S') {
            Col[id].FindLast(h);
            for (int x : temp) {
                --a[x][id];
                Row[x].Update(id, a[x][id]);
                Col[id].Update(x, a[x][id]);
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= m - p + 1; ++i) {
        for (int j = 1; j <= n - p + 1; ++j) {
            int sum = a[i + p - 1][j + p - 1] - a[i + p - 1][j - 1] - a[i - 1][j + p - 1] + a[i - 1][j - 1];
            ans = max(ans, sum);
        }
    }
    cout << ans;
}

Compilation message

ufo.cpp: In constructor 'SegmentTreeMax::SegmentTreeMax(int)':
ufo.cpp:24:9: warning: 'SegmentTreeMax::n' will be initialized after [-Wreorder]
     int n;
         ^
ufo.cpp:23:17: warning:   'std::vector<int> SegmentTreeMax::Max' [-Wreorder]
     vector<int> Max;
                 ^~~
ufo.cpp:26:5: warning:   when initialized here [-Wreorder]
     SegmentTreeMax(int n):n(n), Max(n * 4 + 10) {}
     ^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	62968 KB	Output is correct
2	Correct	62 ms	62968 KB	Output is correct
3	Correct	79 ms	62968 KB	Output is correct
4	Correct	80 ms	63224 KB	Output is correct
5	Correct	177 ms	65016 KB	Output is correct
6	Correct	458 ms	80376 KB	Output is correct
7	Correct	758 ms	103360 KB	Output is correct
8	Correct	757 ms	103576 KB	Output is correct
9	Correct	945 ms	100944 KB	Output is correct
10	Correct	967 ms	103416 KB	Output is correct
11	Correct	805 ms	103180 KB	Output is correct
12	Correct	854 ms	103416 KB	Output is correct
13	Correct	1086 ms	107768 KB	Output is correct
14	Correct	875 ms	103000 KB	Output is correct
15	Correct	1062 ms	103416 KB	Output is correct
16	Correct	739 ms	102956 KB	Output is correct
17	Correct	1501 ms	107768 KB	Output is correct
18	Correct	586 ms	103516 KB	Output is correct
19	Correct	779 ms	108664 KB	Output is correct
20	Correct	1220 ms	153848 KB	Output is correct