제출 #1324039

#제출 시각아이디문제언어결과실행 시간메모리
1324039nguyenkhangninh99Two Antennas (JOI19_antennas)C++20
100 / 100
754 ms59804 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 2e5 + 5, inf = 2e9;

vector<int> add[maxn], del[maxn], qry[maxn];
int ans[maxn], l[maxn], r[maxn];
int a[maxn], b[maxn], h[maxn];
struct SegmentTree{
    struct node{
        int res, lzh, mxh;
    };
    vector<node> t;
    void init(int n){
        t.assign(4 * n + 67, {-1, inf, 0});
    }
    void apply(int id, int val){
        t[id].res = max(t[id].res, t[id].mxh - val);
        t[id].lzh = min(t[id].lzh, val);
    }
    void push(int id){
        apply(id * 2, t[id].lzh);
        apply(id * 2 + 1, t[id].lzh);
        t[id].lzh = inf;
    }
    void pull(int id){
        t[id].res = max(t[id << 1].res, t[id << 1 | 1].res);
        t[id].mxh = max(t[id << 1].mxh, t[id << 1 | 1].mxh);
    }
    void upd(int id, int l, int r, int pos, int type){
        if(l == r){
            t[id].mxh = h[pos] * type;
            return;
        }
        push(id);
        int mid = (l + r) / 2;
        if(pos <= mid) upd(id * 2, l, mid, pos, type);
        else upd(id * 2 + 1, mid + 1, r, pos, type);
        pull(id);
    }    
    void update(int id, int l, int r, int u, int v, int val){
        if(v < l || r < u) return;
        if(u <= l && r <= v){
            apply(id, val);
            return;
        }
        push(id);
        int mid = (l + r) / 2;
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);
        pull(id);
    }
    int get(int id, int l, int r, int u, int v){
        if(v < l || r < u) return -1;
        if(u <= l && r <= v) return t[id].res;
        push(id);
        int mid = (l + r) / 2;
        return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
} st;
 
signed main(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];

    int q; cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> l[i] >> r[i];
        ans[i] = -1;
    }
    for(int it = 0; it < 2; it++){
        for(int i = 1; i <= n; i++){
            add[min(n + 1, i + a[i])].push_back(i);
            del[min(n + 1, i + b[i] + 1)].push_back(i);
        }
        for(int i = 1; i <= q; i++) qry[r[i]].push_back(i);
    
        st.init(n);
        for(int i = 1; i <= n; i++){
            for(int j: add[i]) st.upd(1, 1, n, j, 1);
            for(int j: del[i]) st.upd(1, 1, n, j, 0);
            if(i > a[i]) st.update(1, 1, n, (1ll, i - b[i]), i - a[i], h[i]);
            for(int j: qry[i]) ans[j] = max(ans[j], st.get(1, 1, n, l[j], i));
        }
        reverse(h + 1, h + n + 1);
        reverse(a + 1, a + n + 1);
        reverse(b + 1, b + n + 1);
        for(int i = 1; i <= q; i++){
            l[i] = n - l[i] + 1;
            r[i] = n - r[i] + 1;
            swap(l[i], r[i]);
        }
        for(int i = 1; i <= n; i++) add[i].clear(), del[i].clear(), qry[i].clear();
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...