Submission #992215

#	Time	Username	Problem	Language	Result	Execution time	Memory
992215		hengliao	Two Antennas (JOI19_antennas)	C++17	100 / 100	2324 ms	132548 KiB

antennas

#pragma GCC optimize("Ofast,O3")

#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;

struct maxsegtree{
    vector<multiset<ll>> nodes;
    vll tree, lazy, lazy2;
    ll treelen;
    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcount(treelen)!=1){
            treelen++;
        }
        tree=vll(2*treelen, -inf);
        lazy=vll(2*treelen, -inf);
		lazy2=vll(2*treelen, inf);
        nodes.resize(2*treelen);
    }

    void check(ll idx, ll low, ll high){
        if(lazy[idx]!=-inf){
            if(!nodes[idx].empty()){
                tree[idx]=max(tree[idx], lazy[idx]-(*nodes[idx].begin()));
            }
            push(idx, low, high);
            lazy[idx]=-inf;
        }
		if(lazy2[idx]!=inf){
            if(!nodes[idx].empty()){
                tree[idx]=max(tree[idx], (*prev(nodes[idx].end()))-lazy2[idx]);
            }
            push(idx, low, high);
            lazy2[idx]=inf;
        }
    }

    void push(ll idx, ll low, ll high){
        if(low!=high){
            lazy[2*idx]=max(lazy[2*idx], lazy[idx]);
            lazy[2*idx+1]=max(lazy[2*idx+1], lazy[idx]);
        }
		if(low!=high){
            lazy2[2*idx]=min(lazy2[2*idx], lazy2[idx]);
            lazy2[2*idx+1]=min(lazy2[2*idx+1], lazy2[idx]);
        }
    }

    void update(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
        check(idx, low, high);
        if(low>=qlow && high<=qhigh){
            if(!nodes[idx].empty()){ 
				tree[idx]=max(tree[idx], val-(*nodes[idx].begin()));
				tree[idx]=max(tree[idx], (*prev(nodes[idx].end()))-val);
			}
            lazy[idx]=max(lazy[idx], val);
			lazy2[idx]=min(lazy2[idx], val);
            push(idx, low, high);
            lazy[idx]=-inf;
			lazy2[idx]=inf;
            return;
        }
        if(low>qhigh || high<qlow){
            return;
        }
        ll mid=(low+high)/2;
        update(2*idx, low, mid, qlow, qhigh, val);
        update(2*idx+1, mid+1, high, qlow, qhigh, val);
        tree[idx]=max(tree[2*idx], tree[2*idx+1]);
    }

    void rom(ll idx, ll low, ll high, ll tar, ll val){
        check(idx, low, high);
        if(low>tar || high<tar){
            return;
        }
        if(low<=tar && high>=tar){
            nodes[idx].erase(nodes[idx].find(val));
        }
		if(low!=high){
			ll mid=(low+high)/2;
			rom(2*idx, low, mid, tar, val);
			rom(2*idx+1, mid+1, high, tar, val);
			tree[idx]=max(tree[2*idx], tree[2*idx+1]);
		}
    }

    void ins(ll idx, ll low, ll high, ll tar, ll val){
        check(idx, low, high);
        if(low>tar || high<tar){
            return;
        }
        if(low<=tar && high>=tar){
            nodes[idx].insert(val);
        }
		if(low!=high){
			ll mid=(low+high)/2;
			ins(2*idx, low, mid, tar, val);
			ins(2*idx+1, mid+1, high, tar, val);
			tree[idx]=max(tree[2*idx], tree[2*idx+1]);
		}
    }

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

/*struct minsegtree{
    vector<multiset<ll>> nodes;
    vll tree, lazy;
    ll treelen;
    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcount(treelen)!=1){
            treelen++;
        }
        tree=vll(2*treelen, -inf);
        lazy=vll(2*treelen, inf);
        nodes.resize(2*treelen);
    }

    void check(ll idx, ll low, ll high){
        if(lazy[idx]!=inf){
            if(!nodes[idx].empty()){
                tree[idx]=max(tree[idx], (*prev(nodes[idx].end()))-lazy[idx]);
            }
            push(idx, low, high);
            lazy[idx]=inf;
        }
    }

    void push(ll idx, ll low, ll high){
        if(low!=high){
            lazy[2*idx]=min(lazy[2*idx], lazy[idx]);
            lazy[2*idx+1]=min(lazy[2*idx+1], lazy[idx]);
        }
    }

    void update(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
        check(idx, low, high);
        if(low>=qlow && high<=qhigh){
            if(!nodes[idx].empty()) 
				tree[idx]=max(tree[idx], (*prev(nodes[idx].end()))-val);
            lazy[idx]=min(lazy[idx], val);
            push(idx, low, high);
            lazy[idx]=inf;
            return;
        }
        if(low>qhigh || high<qlow){
            return;
        }
        ll mid=(low+high)/2;
        update(2*idx, low, mid, qlow, qhigh, val);
        update(2*idx+1, mid+1, high, qlow, qhigh, val);
        tree[idx]=max(tree[2*idx], tree[2*idx+1]);
    }

    void rom(ll idx, ll low, ll high, ll tar, ll val){
        check(idx, low, high);
        if(low>tar || high<tar){
            return;
        }
        if(low<=tar && high>=tar){
            nodes[idx].erase(nodes[idx].find(val));
        }
		if(low!=high){
			ll mid=(low+high)/2;
			rom(2*idx, low, mid, tar, val);
			rom(2*idx+1, mid+1, high, tar, val);
			tree[idx]=max(tree[2*idx], tree[2*idx+1]);
		}
    }

    void ins(ll idx, ll low, ll high, ll tar, ll val){
        check(idx, low, high);
        if(low>tar || high<tar){
            return;
        }
        if(low<=tar && high>=tar){
            nodes[idx].insert(val);
        }
		if(low!=high){
			ll mid=(low+high)/2;
			ins(2*idx, low, mid, tar, val);
			ins(2*idx+1, mid+1, high, tar, val);
			tree[idx]=max(tree[2*idx], tree[2*idx+1]);
		}
    }

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

ll n, q;
ll a[mxN], b[mxN], h[mxN];
vector<pll> qry[mxN];
ll ans[mxN];
vector<pll> in[mxN], out[mxN];
maxsegtree seg;
//minsegtree seg2;

void solve(){
	memset(ans, 0, sizeof(ans));
	cin>>n;
    for(ll i=0;i<n;i++){
        cin>>h[i]>>a[i]>>b[i];
		if(i+a[i]<n) in[i+a[i]].pb({h[i], i});
		if(i+b[i]+1<n) out[i+b[i]+1].pb({h[i], i});
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        ll l, r;
        cin>>l>>r;
        l--; r--;
        qry[r].pb({l, i});
    }
	seg.init(n);
	//seg2.init(n);
	for(ll i=0;i<n;i++){
		for(auto &[x, y]:in[i]){
			seg.ins(1, 0, seg.treelen-1, y, x);
			//seg2.ins(1, 0, seg2.treelen-1, y, x);
		}
		for(auto &[x, y]:out[i]){
			seg.rom(1, 0, seg.treelen-1, y, x);
			//seg2.rom(1, 0, seg2.treelen-1, y, x);
		}
		if(i-a[i]>=0){
			seg.update(1, 0, seg.treelen-1, max(i-b[i], 0LL), i-a[i], h[i]);
			//seg2.update(1, 0, seg2.treelen-1, max(i-b[i], 0LL), i-a[i], h[i]);
		}
		for(auto &[x, y]:qry[i]){
			ll re=seg.getmax(1, 0, seg.treelen-1, x, i);
			//ll re2=seg2.getmax(1, 0, seg2.treelen-1, x, i);
			if(re==-inf){
				ans[y]=-1;
			}
			else{
				ans[y]=re;
			}
		}
	}
	for(ll i=0;i<q;i++){
		cout<<ans[i]<<'\n';
	}

}

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

	solve();
	return 0;
}

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