Submission #592670

#	Time	Username	Problem	Language	Result	Execution time	Memory
592670		pakhomovee	Two Antennas (JOI19_antennas)	C++17	0 / 100	3064 ms	25896 KiB

antennas

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65