답안 #102579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102579	2019-03-26T02:53:32 Z	nickyrio	UFO (IZhO14_ufo)	C++17	95 / 100	1396 ms	113272 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;
#define pp pair<int, int>

const int N = 3e5 + 10;
const int MAXH = 1e6 + 100;

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:26:9: warning: 'SegmentTreeMax::n' will be initialized after [-Wreorder]
     int n;
         ^
ufo.cpp:25:17: warning:   'std::vector<int> SegmentTreeMax::Max' [-Wreorder]
     vector<int> Max;
                 ^~~
ufo.cpp:28:5: warning:   when initialized here [-Wreorder]
     SegmentTreeMax(int n):n(n), Max(n * 4 + 10) {}
     ^~~~~~~~~~~~~~

Subtask #1

95.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	19072 KB	Output is correct
2	Correct	21 ms	19072 KB	Output is correct
3	Correct	22 ms	19200 KB	Output is correct
4	Correct	48 ms	19668 KB	Output is correct
5	Correct	140 ms	21752 KB	Output is correct
6	Correct	431 ms	39900 KB	Output is correct
7	Correct	802 ms	67720 KB	Output is correct
8	Correct	488 ms	63992 KB	Output is correct
9	Correct	761 ms	60664 KB	Output is correct
10	Correct	736 ms	63224 KB	Output is correct
11	Correct	551 ms	62328 KB	Output is correct
12	Correct	739 ms	63068 KB	Output is correct
13	Correct	913 ms	68364 KB	Output is correct
14	Correct	770 ms	62520 KB	Output is correct
15	Correct	944 ms	64648 KB	Output is correct
16	Correct	565 ms	64632 KB	Output is correct
17	Correct	1396 ms	72752 KB	Output is correct
18	Correct	605 ms	64992 KB	Output is correct
19	Correct	620 ms	69752 KB	Output is correct
20	Runtime error	142 ms	113272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)