제출 #1149419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149419		daoquanglinh2007	Two Antennas (JOI19_antennas)	C++20	100 / 100	579 ms	38500 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2e5, LIM = 1e9, inf = 1e18;

int N, Q, H[NM+5], A[NM+5], B[NM+5];
pii st[4*NM+5];
int lazy[4*NM+5];
vector <int> arr[NM+5];
vector <pii> qry[NM+5];
int ans[NM+5];

pii merge(pii a, pii b){
    pii c;
    c.fi = min(a.fi, b.fi);
    c.se = max(a.se, b.se);
    return c;
}

void build(int id, int l, int r){
    lazy[id] = -inf;
    if (l == r){
        st[id].fi = +inf;
        st[id].se = -inf;
        return;
    }
    int mid = (l+r)/2;
    build(2*id, l, mid);
    build(2*id+1, mid+1, r);
    st[id] = merge(st[2*id], st[2*id+1]);
}

void down(int id){
    if (lazy[id] < 0) return;
    st[2*id].se = max(st[2*id].se, lazy[id]-st[2*id].fi);
    st[2*id+1].se = max(st[2*id+1].se, lazy[id]-st[2*id+1].fi);
    lazy[2*id] = max(lazy[2*id], lazy[id]);
    lazy[2*id+1] = max(lazy[2*id+1], lazy[id]);
    lazy[id] = -inf;
}

void update(int id, int l, int r, int i, int val){
    if (i < l || i > r) return;
    if (l == r){
        st[id].fi = val;
        return;
    }
    down(id);
    int mid = (l+r)/2;
    update(2*id, l, mid, i, val);
    update(2*id+1, mid+1, r, i, val);
    st[id] = merge(st[2*id], st[2*id+1]);
}

void maximize(int id, int l, int r, int u, int v, int val){
    if (v < l || u > r) return;
    if (l >= u && r <= v){
        st[id].se = max(st[id].se, val-st[id].fi);
        lazy[id] = max(lazy[id], val);
        return;
    }
    down(id);
    int mid = (l+r)/2;
    maximize(2*id, l, mid, u, v, val);
    maximize(2*id+1, mid+1, r, u, v, val);
    st[id] = merge(st[2*id], st[2*id+1]);
}

pii get(int id, int l, int r, int u, int v){
    if (v < l || u > r) return mp(+inf, -inf);
    if (l >= u && r <= v) return st[id];
    down(id);
    int mid = (l+r)/2;
    return merge(get(2*id, l, mid, u, v), get(2*id+1, mid+1, r, u, v));
}

void solve(){
    build(1, 1, N);
    for (int j = 1; j <= N; j++){
        for (int i : arr[j]){
            if (i > 0) update(1, 1, N, i, H[i]);
            else update(1, 1, N, -i, +inf);
        }
        if (j-A[j] > 0){
            int l = max(j-B[j], 1LL), r = j-A[j];
            maximize(1, 1, N, l, r, H[j]);
        }
        for (pii p : qry[j]){
            int i = p.fi, id = p.se;
            ans[id] = max(ans[id], get(1, 1, N, i, j).se);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> H[i] >> A[i] >> B[i];
        if (i+A[i] <= N){
            arr[i+A[i]].push_back(i);
            if (i+B[i]+1 <= N) arr[i+B[i]+1].push_back(-i);
        }
    }
    cin >> Q;
    for (int i = 1; i <= Q; i++){
        int l, r; cin >> l >> r;
        qry[r].push_back(mp(l, i));
        ans[i] = -inf;
    }
    solve();
    for (int i = 1; i <= N; i++) H[i] = LIM+1-H[i];
    solve();
    for (int i = 1; i <= Q; i++)
        if (ans[i] < 0) cout << "-1\n"; else cout << ans[i] << '\n';
    return 0;
}

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