Submission #1296419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296419		jahongir	Two Antennas (JOI19_antennas)	C++20	100 / 100	350 ms	40536 KiB

antennas

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,
					 tree_order_statistics_node_update>;

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()  

const int inf = 1e9;

struct Node{
    int h,H,d;
    Node(int h = -inf, int H = -inf, int d = -inf):h(h),H(H),d(d){;}
    Node operator +(const Node &o) const{
        Node res;
        res.h = max(h,o.h);
        res.d = max(d,o.d);
        return res;
    }
};

struct SegTree{
    vector<Node> st; int sz;
    SegTree(int n): st((n<<2)),sz(n){;}

    void apply(int i, int H){
        st[i].d = max(st[i].d,H+st[i].h);
        st[i].H = max(st[i].H,H);
    }

    void push(int i){
        if(st[i].H != -inf){
            apply(i<<1,st[i].H);
            apply(i<<1|1,st[i].H);
            st[i].H = -inf;
        }
    }

    void update(int i, int l, int r, int k, int val){
        if(l==r){
            if(val) st[i].h = val;
            else st[i].h = -inf; return;
        }
        int m = (l+r)>>1; push(i);
        if(k <= m) update(i<<1,l,m,k,val);
        else update(i<<1|1,m+1,r,k,val);
        st[i] = st[i<<1] + st[i<<1|1];
    }

    void update(int k, int val){
        update(1,1,sz,k,val);
    }

    void update2(int i, int l, int r, int s, int e, int val){
        if(r < s || l > e) return;
        if(s <= l && r <= e){apply(i,val); return;}
        int m = (l+r)>>1; push(i);
        update2(i<<1,l,m,s,e,val);
        update2(i<<1|1,m+1,r,s,e,val);
        st[i] = st[i<<1] + st[i<<1|1];
    }

    void update2(int l, int r, int val){
        update2(1,1,sz,l,r,val);
    }

    int get(int i, int l, int r, int s, int e){
        if(r < s || l > e) return -inf;
        if(s <= l && r <= e) return st[i].d;
        int m = (l+r)>>1; push(i);
        return max(get(i<<1,l,m,s,e),get(i<<1|1,m+1,r,s,e));
    }

    int get(int l, int r){
        return get(1,1,sz,l,r);
    }
};


const int mxn = 2e5+1;
int arr[mxn][3], res[mxn];
vector<pi> qu[mxn], vec[mxn];


void solve(){
    int n,q; cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    cin >> q;
    for(int i = 1; i <= q; i++){
        int l,r; cin >> l >> r; qu[r].push_back({i,l});
    }

    SegTree st(n), st2(n);
    for(int i = 1; i <= n; i++){
        for(auto [j,val] : vec[i]){
            st.update(j,-val); st2.update(j,val);
        }
        int l = max(1,i-arr[i][2]);
        int r = i-arr[i][1];
        if(l <= r){
            st.update2(l,r,arr[i][0]);
            st2.update2(l,r,-arr[i][0]);
        }

        for(auto [j,l] : qu[i])
            res[j] = max(st.get(l,i),st2.get(l,i));

        if(i + arr[i][1] <= n) vec[i+arr[i][1]].push_back({i,arr[i][0]});
        if(i + arr[i][2] + 1 <= n) vec[i+arr[i][2]+1].push_back({i,0});
    }

    for(int i = 1; i <= q; i++)
        cout << max(-1,res[i]) << '\n';
}




signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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