Submission #144386

#	Time	Username	Problem	Language	Result	Execution time	Memory
144386		osaaateiasavtnl	Two Antennas (JOI19_antennas)	C++14	100 / 100	814 ms	69704 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int n, q;
struct E { int h, a, b; } a[N];
namespace OP {
int mn[N << 2], mx[N << 2], mn1[N << 2], mx1[N << 2], tans[N << 2];
void rec(int v) { tans[v] = max(mx[v] - mn1[v], mx1[v] - mn[v]); }
int get(int v) { return max(mx[v] - mn1[v], mx1[v] - mn[v]); }
void push(int v) {
    for (int i = v * 2 + 1; i <= v * 2 + 2; ++i) {
        mn[i] = min(mn[i], mn[v]); mx[i] = max(mx[i], mx[v]);
        tans[i] = max(tans[i], get(i));
    }
    mn[v] = INF; mx[v] = -INF;
}
void relax(int v) {
    tans[v] = max(tans[v * 2 + 1], tans[v * 2 + 2]);
    mn1[v] = min(mn1[v * 2 + 1], mn1[v * 2 + 2]);
    mx1[v] = max(mx1[v * 2 + 1], mx1[v * 2 + 2]);
}
void upd(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl) return;
    if (l <= tl && tr <= r) { 
        mn[v] = min(mn[v], x); mx[v] = max(mx[v], x); 
        tans[v] = max(tans[v], get(v));
        return; 
    }
    int tm = (tl + tr) >> 1;
    push(v);
    upd(v * 2 + 1, tl, tm, l, r, x); upd(v * 2 + 2, tm + 1, tr, l, r, x);
    relax(v);
}
void open(int v, int tl, int tr, int p) {
    if (tl == tr) { mn[v] = INF; mx[v] = -INF; mn1[v] = mx1[v] = a[p].h; tans[v] = -INF; return; }
    int tm = (tl + tr) >> 1;
    push(v);
    if (p <= tm) open(v * 2 + 1, tl, tm, p); 
    else open(v * 2 + 2, tm + 1, tr, p);
    relax(v);
}
int close(int v, int tl, int tr, int p) {
    if (tl == tr) { int ans = tans[v]; mn[v] = mn1[v] = INF; mx[v] = mx1[v] = -INF; tans[v] = -INF; return ans; }
    int tm = (tl + tr) >> 1;
    push(v);
    int t; 
    if (p <= tm) t = close(v * 2 + 1, tl, tm, p); 
    else t = close(v * 2 + 2, tm + 1, tr, p);
    relax(v); return t;
}   
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return -INF;
    if (l <= tl && tr <= r) return tans[v];
    int tm = (tl + tr) >> 1;
    push(v);
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}
};
vector <ii> mem[N];
vector <int> open[N], close[N];
int tree[N << 2];
void add(int v, int tl, int tr, int p, int x) {
    if (tl == tr) { tree[v] = x; return; }
    int tm = (tl + tr) >> 1;
    if (p <= tm) add(v * 2 + 1, tl, tm, p, x);
    else add(v * 2 + 2, tm + 1, tr, p, x);
    tree[v] = max(tree[v * 2 + 1], tree[v * 2 + 2]);
}
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return -INF;
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) >> 1;
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}
void open_(int i) { OP::open(0, 0, N, i); }
void close_(int i) { add(0, 0, N, i, OP::close(0, 0, N, i)); }
void add(int i) {
    int l = i - a[i].b, r = i - a[i].a;
    if (r < 0) return;
    l = max(l, 0ll);
    OP::upd(0, 0, N, l, r, a[i].h);
}
int get(int l, int r) { return max(get(0, 0, N, l, r), OP::get(0, 0, N, l, r)); }
int ans[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 0; i < (N << 2); ++i) { OP::mn[i] = OP::mn1[i] = INF; OP::mx[i] = OP::mx1[i] = -INF; OP::tans[i] = -INF; tree[i] = -INF; }
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].h >> a[i].a >> a[i].b; 
        if (i + a[i].a < N) open[i + a[i].a].app(i); 
        if (i + a[i].b + 1 < N) close[i + a[i].b + 1].app(i); 
    }
    cin >> q;
    for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; mem[r].app({l, i}); }
    for (int i = 1; i <= n; ++i) {
        for (int e : open[i]) open_(e);
        for (int e : close[i]) close_(e);
        add(i);
        for (auto e : mem[i]) ans[e.second] = get(e.first, i);
    }
    for (int i = 0; i < q; ++i) { 
        if (ans[i] < 0) cout << "-1\n";
        else cout << ans[i] << '\n';
    }
}   

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