oj.uz

Submission #592670

# Submission time Handle Problem Language Result Execution time Memory
592670 2022-07-09T12:48:26 Z pakhomovee Two Antennas (JOI19_antennas) C++17
0 / 100
 3000 ms 25896 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <deque>
#include <functional>
#include <set>
#include <queue>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <complex>


using namespace std;

struct antenna {
    int a, b, h;

    antenna() {}
    antenna(int a, int b, int h): a(a), b(b), h(h) {}
};

const int maxn = 3e5;
const int inf = 1e9 + 10;
int gta[maxn];
int lsa[maxn];
int h[maxn];
vector<antenna> a;

void init() {
    fill(gta, gta + maxn, -inf);
    fill(lsa, lsa + maxn, -inf);
    fill(h, h + maxn, -1);
}

void upd(int l, int r, int x) {
    for (int i = l; i < r; ++i) {
        if (h[i] != -1) {
            gta[i] = max(gta[i], x - h[i]);
            lsa[i] = max(lsa[i], h[i] - x);
        }
    }
}

void enable(int j) {
    h[j] = a[j].h;
}

void disable(int j) {
    h[j] = a[j].h;
}

int get(int l, int r) {
    int res = -inf;
    for (int i = l; i < r; ++i) {
        res = max(res, gta[i]);
        res = max(res, lsa[i]);
    }
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        int x, y, h;
        cin >> h >> x >> y;
        a[i] = antenna(x, y, h);
    }
    vector<vector<pair<int, int>>> queries(n + 1);
    vector<vector<int>> add(n + 1);
    vector<vector<int>> del(n + 1);
    int q;
    cin >> q;
    vector<int> ans(q, -1);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[r - 1].push_back({ l - 1, i });
    }
    init();
    for (int i = 0; i < n; ++i) {
        add[min(i + a[i].a, n)].push_back(i);
        del[min(i + a[i].b + 1, n)].push_back(i);
        for (int j : add[i]) {
            enable(j);
        }
        for (int j : del[i]) {
            disable(j);
        }
        int L = max(0, i - a[i].b);
        int R = max(0, i - a[i].a + 1);
        upd(L, R, a[i].h);
        for (auto [l, j] : queries[i]) {
            ans[j] = max(ans[j], get(l, i + 1));
        }
    }
    for (int i : ans) {
        cout << i << '\n';
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 25896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3788 KB Output isn't correct
2 Halted 0 ms 0 KB -