Submission #780876

#	Time	Username	Problem	Language	Result	Execution time	Memory
780876		TeaTime	Two Antennas (JOI19_antennas)	C++17	100 / 100	714 ms	88040 KiB

antennas

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 200'100, INF = 2'000'000'000;
struct tow {
    ll h, a, b;
};

struct qs{
    ll l, r, ind;
};

vector<tow> vec;
vector<qs> queries[SZ];
ll n, q;

ll pushmx[SZ * 8], pushmn[SZ * 8], opt[SZ * 4], mx[SZ * 4], mn[SZ * 4];

void push(int v) {
    opt[v] = max(opt[v], pushmx[v] - mn[v]);
    opt[v] = max(opt[v], mx[v] - pushmn[v]);

    pushmx[v * 2 + 1] = max(pushmx[v * 2 + 1], pushmx[v]);
    pushmx[v * 2 + 2] = max(pushmx[v * 2 + 2], pushmx[v]);

    pushmn[v * 2 + 1] = min(pushmn[v * 2 + 1], pushmn[v]);
    pushmn[v * 2 + 2] = min(pushmn[v * 2 + 2], pushmn[v]);

    pushmx[v] = -INF;
    pushmn[v] = INF;
}

void toggle(int v, int l, int r, int pos) {
    push(v);
    if (l == r - 1) {
        if (mx[v] == -INF) {
            mx[v] = mn[v] = vec[l].h;
        } else {
            mx[v] = -INF;
            mn[v] =  INF;
        }
    } else {
        push(v * 2 + 1);
        push(v * 2 + 2);
        int mid = (l + r) / 2;
        if (pos < mid) {
            toggle(v * 2 + 1, l, mid, pos);
        } else {
            toggle(v * 2 + 2, mid, r, pos);
        }

        mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
        mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]);
        opt[v] = max(opt[v * 2 + 1], opt[v * 2 + 2]);
    }
}

ll ask(int v, int l, int r, int askl, int askr) {
    push(v);
    if (l >= askr || r <= askl) return -1;

    if (askl <= l && r <= askr) {
        return opt[v];
    }

    int mid = (l + r) / 2;
    return max(ask(v * 2 + 1, l, mid, askl, askr), ask(v * 2 + 2, mid, r, askl, askr));
}

void upd(int v, int l, int r, int askl, int askr, ll val) {
    push(v);
    if (l >= askr || r <= askl) return;

    if (askl <= l && r <= askr) {
        pushmn[v] = min(pushmn[v], val);
        pushmx[v] = max(pushmx[v], val);
        push(v);
        return;
    }

    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, askl, askr, val);
    upd(v * 2 + 2, mid, r, askl, askr, val);
    push(v * 2 + 1);
    push(v * 2 + 2);

    mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
    mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]);
    opt[v] = max(opt[v * 2 + 1], opt[v * 2 + 2]);
}

vector<ll> togler[SZ * 2 + 100];

int main() {
    fastInp;

    cin >> n;

    vec.resize(n);
    for (auto &c : vec) cin >> c.h >> c.a >> c.b;

    cin >> q;

    for (int i = 0; i < q; i++) {
        ll l, r;
        cin >> l >> r;
        l--; r--;
        queries[r].push_back({l, r, i});
    }

    for (int i = 0; i < SZ * 8; i++) {
        pushmx[i] = -INF;
        pushmn[i] = INF;
    }

    for (int i = 0; i < SZ * 4; i++) {
        opt[i] = -1;
        mx[i] = -INF;
        mn[i] = INF;
    }

    
    vector<ll> ans(q);
    for (int i = 0; i < n; i++) {
        for (auto c : togler[i]) {
            toggle(0, 0, n, c);
        }

        ll l = i - vec[i].b, r = i - vec[i].a;
        l = max(l, 0ll);

        upd(0, 0, n, l, r + 1, vec[i].h);

        for (auto c : queries[i]) {
            ans[c.ind] = ask(0, 0, n, c.l, c.r + 1);
        }

        togler[i + vec[i].a].push_back(i);
        togler[i + vec[i].b + 1].push_back(i);
    }

    for (auto c : ans) cout << c << "\n";

    return 0;
}

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