oj.uz

Submission #102581

# Submission time Handle Problem Language Result Execution time Memory
102581 2019-03-26T02:59:56 Z nickyrio UFO (IZhO14_ufo) C++17
100 / 100
 1501 ms 153848 KB 
//
//  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

# Verdict Execution time Memory 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