답안 #102580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102580	2019-03-26T02:54:34 Z	nickyrio	UFO (IZhO14_ufo)	C++17	95 / 100	1459 ms	263168 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 + 100);
    }
    
    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	19 ms	19072 KB	Output is correct
2	Correct	19 ms	19072 KB	Output is correct
3	Correct	24 ms	19320 KB	Output is correct
4	Correct	39 ms	19576 KB	Output is correct
5	Correct	138 ms	22964 KB	Output is correct
6	Correct	420 ms	36928 KB	Output is correct
7	Correct	856 ms	95532 KB	Output is correct
8	Correct	640 ms	95652 KB	Output is correct
9	Correct	813 ms	75048 KB	Output is correct
10	Correct	879 ms	95608 KB	Output is correct
11	Correct	746 ms	102660 KB	Output is correct
12	Correct	898 ms	95648 KB	Output is correct
13	Correct	963 ms	99960 KB	Output is correct
14	Correct	825 ms	102284 KB	Output is correct
15	Correct	970 ms	95528 KB	Output is correct
16	Correct	737 ms	102392 KB	Output is correct
17	Correct	1459 ms	99940 KB	Output is correct
18	Correct	579 ms	102780 KB	Output is correct
19	Correct	781 ms	136824 KB	Output is correct
20	Runtime error	261 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)