Submission #951605

#	Time	Username	Problem	Language	Result	Execution time	Memory
951605		hengliao	Two Antennas (JOI19_antennas)	C++14	0 / 100	146 ms	28944 KiB

antennas

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll inf=1e18;

ll h[mxN];
ll a[mxN];
ll b[mxN];
ll n, q;
vll add[mxN];
vll minu[mxN];

struct segtree{
    vll tree;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcountll(treelen)!=1){
            treelen++;
        }
        tree=vll(2*treelen, 0);
    }

    void update(ll idx, ll val){
        ll tar=treelen+idx;
        tree[tar]=val;
        tar/=2;
        while(tar>0){
            tree[tar]=max(tree[2*tar], tree[2*tar+1]);
            tar/=2;
        }
    }

    ll getmax(ll idx, ll low, ll high, ll qlow, ll qhigh){
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return 0;
        }
        ll mid=(low+high)/2;
        return max(getmax(2*idx, low, mid, qlow, qhigh), 
            getmax(2*idx+1, mid+1, high, qlow, qhigh));
    }
};

struct segtree2{
    vll tree;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcountll(treelen)!=1){
            treelen++;
        }
        tree=vll(2*treelen, inf);
    }

    void update(ll idx, ll val){
        ll tar=treelen+idx;
        tree[tar]=val;
        tar/=2;
        while(tar>0){
            tree[tar]=min(tree[2*tar], tree[2*tar+1]);
            tar/=2;
        }
    }

    ll getmin(ll idx, ll low, ll high, ll qlow, ll qhigh){
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return inf;
        }
        ll mid=(low+high)/2;
        return min(getmin(2*idx, low, mid, qlow, qhigh), 
            getmin(2*idx+1, mid+1, high, qlow, qhigh));
    }
};

segtree seg1;
segtree2 seg2;

ll solve2(ll l, ll r){
    seg1.init(n);
    seg2.init(n);
    /*for(auto it:seg2.tree){
        cout<<it<<' ';
    }
    cout<<'\n';*/
    for(ll i=l;i<=r;i++){
        add[i].clear();
        minu[i].clear();
    }
    ll re=-1;
    for(ll i=l;i<=r;i++){
        for(auto it:add[i]){
            seg1.update(it, h[it]);
            seg2.update(it, h[it]);
        }
        /*
        for(auto it:minu[i]){
            seg1.update(it, 0);
            seg2.update(it, inf);
        }*/
        if(i+a[i]<=r){
            add[i+a[i]].pb(i);
        }
        if(i+b[i]+1<=r){
            minu[i+b[i]+1].pb(i);
        }
        ll low=i-b[i], high=i-a[i];
        low=max(low, l);
        //cout<<i<<' '<<low<<' '<<high<<'\n';
        if(high<low) continue;
        ll mn=seg2.getmin(1, 0, seg2.treelen-1, low, high);
        //cout<<mn<<'\n';
        if(mn!=inf){
            re=max(re, abs(h[i]-mn));
        }
        ll mx=seg1.getmax(1, 0, seg1.treelen-1, low, high);
        //cout<<mx<<'\n';
        if(mx!=0){
            re=max(re, abs(h[i]-mx));
        }
    }
    return re;
}

void solve(){
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>h[i]>>a[i]>>b[i];
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        ll l, r;
        cin>>l>>r;
        l--; r--;
        cout<<solve2(l, r);
        if(i<q-1) cout<<'\n';
    }
}

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

    solve();
    return 0;
}

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