Submission #260116

#	Time	Username	Problem	Language	Result	Execution time	Memory
260116		keko37	Two Antennas (JOI19_antennas)	C++14	100 / 100	908 ms	60024 KiB

antennas

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 200005;
const llint INF = 1000000000000000000LL;

int n, q, ofs = 1;
int h[MAXN], a[MAXN], b[MAXN], res[MAXN];
vector <int> v[MAXN];
vector <pi> r[MAXN];

struct node {
    llint sol, mn, mx, prop_mn, prop_mx;
    node () {
        sol = -1;
        mn = prop_mn = INF;
        mx = prop_mx = -INF;
    }
    node (llint _sol, llint _mn, llint _mx, llint _prop_mn, llint _prop_mx) {
        sol = _sol; mn = _mn; mx = _mx; prop_mn = _prop_mn, prop_mx = _prop_mx;
    }
} t[MAXN * 4];

void propagate (int x) {
    if (x < ofs) {
        t[2 * x].prop_mn = min(t[2 * x].prop_mn, t[x].prop_mn);
        t[2 * x].prop_mx = max(t[2 * x].prop_mx, t[x].prop_mx);
        t[2 * x + 1].prop_mn = min(t[2 * x + 1].prop_mn, t[x].prop_mn);
        t[2 * x + 1].prop_mx = max(t[2 * x + 1].prop_mx, t[x].prop_mx);
    }
    if (t[x].prop_mn <= t[x].mx) t[x].sol = max(t[x].sol, t[x].mx - t[x].prop_mn);
    if (t[x].mn <= t[x].prop_mx) t[x].sol = max(t[x].sol, t[x].prop_mx - t[x].mn);
    t[x].prop_mn = INF;
    t[x].prop_mx = -INF;
}

node spoji (node x, node y) {
    return node(max(x.sol, y.sol), min(x.mn, y.mn), max(x.mx, y.mx), min(x.prop_mn, y.prop_mn), max(x.prop_mx, y.prop_mx));
}

void update_prop (int x, int from, int to, int lo, int hi, llint val) {
    propagate(x);
    if (from <= lo && hi <= to) {
        t[x].prop_mn = min(t[x].prop_mn, val);
        t[x].prop_mx = max(t[x].prop_mx, val);
        propagate(x);
        return;
    }
    if (to < lo || hi < from) return;
    update_prop(2 * x, from, to, lo, (lo + hi) / 2, val);
    update_prop(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi, val);
    t[x] = spoji(t[2 * x], t[2 * x + 1]);
}

void update_akt (int x, int pos, int lo, int hi, llint val) {
    propagate(x);
    if (pos == lo && pos == hi) {
        if (val == 0) {
            t[x].mn = INF;
            t[x].mx = -INF;
        } else {
            t[x].mn = min(t[x].mn, val);
            t[x].mx = max(t[x].mx, val);
        }
        propagate(x);
        return;
    }
    if (pos < lo || hi < pos) return;
    update_akt(2 * x, pos, lo, (lo + hi) / 2, val);
    update_akt(2 * x + 1, pos, (lo + hi) / 2 + 1, hi, val);
    t[x] = spoji(t[2 * x], t[2 * x + 1]);
}

llint upit (int x, int from, int to, int lo, int hi) {
    propagate(x);
    if (from <= lo && hi <= to) return t[x].sol;
    if (to < lo || hi < from) return -1;
    return max(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

void sweep () {
    for (int i = 1; i <= n; i++) {
        int lo = i + a[i], hi = i + b[i];
        if (lo <= n) v[lo].push_back(i);
        if (hi + 1 <= n) v[hi + 1].push_back(-i);
    }
    for (int i = 1; i <= n; i++) {
        for (auto x : v[i]) {
            if (x > 0) {
                update_akt(1, x, 0, ofs - 1, h[x]);
            } else {
                update_akt(1, -x, 0, ofs - 1, 0);
            }
        }
        int lo = i - b[i], hi = i - a[i];
        if (1 <= hi) {
            lo = max(lo, 1);
            update_prop(1, lo, hi, 0, ofs - 1, h[i]);
        }
        for (auto par : r[i]) {
            int lef = par.first, ind = par.second;
            res[ind] = upit(1, lef, i, 0, ofs - 1);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    while (ofs < n + 1) ofs *= 2;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        r[b].push_back({a, i});
    }
    sweep();
    for (int i = 1; i <= q; i++) {
        cout << res[i] << '\n';
    }
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65