oj.uz

Submission #102579

# Submission time Handle Problem Language Result Execution time Memory
102579 2019-03-26T02:53:32 Z nickyrio UFO (IZhO14_ufo) C++17
95 / 100
 1396 ms 113272 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;
#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

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