Submission #960023

#	Time	Username	Problem	Language	Result	Execution time	Memory
960023		Tuanlinh123	Two Antennas (JOI19_antennas)	C++17	100 / 100	311 ms	44264 KiB

antennas

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=200005, inf=2e9;
ll h[maxn], a[maxn], b[maxn], ans[maxn];
vector <pll> Q[maxn];
vector <ll> H[maxn];

namespace SegTree
{
    ll n, ans[maxn*4], Max[maxn*4], Min[maxn*4], lmx[maxn*4], lmn[maxn*4];

    void build(ll i, ll Start, ll End)
    {
        lmx[i]=Max[i]=-1, lmn[i]=Min[i]=inf, ans[i]=-1;
        if (Start==End) return;
        ll mid=(Start+End)/2;
        build(i*2, Start, mid);
        build(i*2+1, mid+1, End);
    }
    void init(ll sz){n=sz, build(1, 1, n);}

    void Move(ll i)
    {
        if (lmx[i]>-1)
        {
            ll t=lmx[i]; lmx[i]=-1;
            lmx[i*2]=max(lmx[i*2], t);
            ans[i*2]=max(ans[i*2], t-Min[i*2]);
            lmx[i*2+1]=max(lmx[i*2+1], t);
            ans[i*2+1]=max(ans[i*2+1], t-Min[i*2+1]);
        }
        if (lmn[i]<inf)
        {
            ll t=lmn[i]; lmn[i]=inf;
            lmn[i*2]=min(lmn[i*2], t);
            ans[i*2]=max(ans[i*2], Max[i*2]-t);
            lmn[i*2+1]=min(lmn[i*2+1], t);
            ans[i*2+1]=max(ans[i*2+1], Max[i*2+1]-t);
        }
    }

    void toggle(ll i, ll Start, ll End, ll idx)
    {
        if (Start>idx || End<idx) return;
        if (Start==End)
        {
            if (Max[i]>=0) Max[i]=-1, Min[i]=inf;
            else Max[i]=Min[i]=h[Start];
            return;
        }
        ll mid=(Start+End)/2; Move(i);
        if (idx<=mid) toggle(i*2, Start, mid, idx);
        else toggle(i*2+1, mid+1, End, idx);
        Max[i]=max(Max[i*2], Max[i*2+1]);
        Min[i]=min(Min[i*2], Min[i*2+1]);
    }
    void toggle(ll idx) {
        // cout << "toggle: " << idx << "\n";
        toggle(1, 1, n, idx);}

    void update(ll i, ll Start, ll End, ll l, ll r, ll v)
    {
        if (Start>r || End<l) return;
        if (Start>=l && End<=r)
        {
            lmx[i]=max(lmx[i], v), lmn[i]=min(lmn[i], v);
            ans[i]=max({ans[i], v-Min[i], Max[i]-v});
            return;
        }
        ll mid=(Start+End)/2; Move(i);
        if (mid>=l) update(i*2, Start, mid, l, r, v);
        if (mid+1<=r) update(i*2+1, mid+1, End, l, r, v);
        ans[i]=max({ans[i], ans[i*2], ans[i*2+1]});
    }
    void update(ll l, ll r, ll v) {
        // cout << "update: " << l << " " << r << " " << v << "\n";
        update(1, 1, n, l, r, v);}

    ll query(ll i, ll Start, ll End, ll l, ll r)
    {
        if (Start>r || End<l) return -1;
        if (Start>=l && End<=r) return ans[i];
        ll mid=(Start+End)/2; Move(i);
        if (mid<l) return query(i*2+1, mid+1, End, l, r);
        if (mid+1>r) return query(i*2, Start, mid, l, r);
        return max(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
    }
    ll query(ll l, ll r){
        // cout << "query: " << l << " " << r << " " << query(1, 1, n, l, r) << "\n";
        return query(1, 1, n, l, r);}
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=1; i<=n; i++)
    {
        cin >> h[i] >> a[i] >> b[i];
        if (i+a[i]<=n) H[i+a[i]].pb(i);
        if (i+b[i]+1<=n) H[i+b[i]+1].pb(i);
    }
    ll q; cin >> q;
    for (ll i=1; i<=q; i++)
    {
        ll l, r; cin >> l >> r, ans[i]=-1;
        Q[r].pb({l, i});
    }
    SegTree::init(n);
    for (ll i=1; i<=n; i++)
    {
        // cout << "order: " << i << "\n";
        for (ll x:H[i]) SegTree::toggle(x);
        SegTree::update(i-b[i], i-a[i], h[i]);
        for (auto [l, idx]:Q[i])
            ans[idx]=max(ans[idx], SegTree::query(l, i));
    }
    for (ll i=1; i<=q; i++) cout << ans[i] << " ";
}

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