Submission #1296388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296388		jahongir	Two Antennas (JOI19_antennas)	C++20	22 / 100	155 ms	22064 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()  

#define int ll

const int mxn = 2e5+2, inf = 2e9;
int arr[mxn][3];
int st[1<<19],st2[1<<19];
vector<pi> qu[mxn];

void update(int i, int l, int r, int k, int val){
    if(l==r){
        st[i] = (val?val:-inf);
        st2[i] = (val?val:inf); return;
    }
    int m = (l+r)>>1;
    if(k <= m) update(i<<1,l,m,k,val);
    else update(i<<1|1,m+1,r,k,val);
    st[i] = max(st[i<<1],st[i<<1|1]);
    st2[i] = min(st2[i<<1],st2[i<<1|1]);
}

pi get(int i, int l, int r, int s, int e){
    if(r < s || l > e) return {-inf,inf};
    if(s <= l && r <= e) return {st[i],st2[i]};
    int m = (l+r)>>1;
    pi r1 = get(i<<1,l,m,s,e);
    pi r2 = get(i<<1|1,m+1,r,s,e);
    return {max(r1.first,r2.first),min(r1.second,r2.second)};
}


void solve(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i][2] >> arr[i][0] >> arr[i][1];
        if(i+arr[i][0] <= n) qu[i+arr[i][0]].push_back({i,arr[i][2]});
        if(i+arr[i][1]+1 <= n) qu[i+arr[i][1]+1].push_back({i,0});
    }

    fill(st,st+(1<<19),-inf);
    fill(st2,st2+(1<<19),inf);

    ll ans = -1;
    for(int i = 1; i <= n; i++){
        for(auto [j,x] : qu[i]) update(1,1,n,j,x);

        int l = max(1ll,i-arr[i][1]);
        int r = min(i-1,i-arr[i][0]);
        if(l <= r){
            auto [up,low] = get(1,1,n,l,r);
            ans = max(ans,(ll) up-arr[i][2]);
            ans = max(ans,(ll) arr[i][2]-low);
        }
    }   

    cout << ans;
}




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

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