Submission #1098625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098625		flyingkite	Two Antennas (JOI19_antennas)	C++17	100 / 100	646 ms	77416 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll block = 100;
ll n,q;
ll h[N], a[N], b[N], res[N];
vector<pll>sweep[N], t[N];
struct ccjv{ll mx = -1, mn = -1, ans = -inf;};
struct segment_tree{
	ll n;
	vector<ccjv>st;
	vector<pll>lz;
	void init(ll _n){
		n = _n;
		st.resize(4 * n + 10); lz.resize(4 * n + 10, make_pair(-inf, inf));
	}
	ccjv merge(const ccjv &a, const ccjv &b){
		ccjv res;
		res.ans = max(a.ans, b.ans);
		if(a.mn == -1) res.mn = b.mn;
		else if(b.mn == -1) res.mn = a.mn;
		else res.mn = min(a.mn, b.mn);
		if(a.mx == -1) res.mx = b.mx;
		else if(b.mx == -1) res.mx = a.mx;
		else res.mx = max(a.mx, b.mx);
		return res;
	}
	void down(ll id, ll l, ll r){
		if(lz[id].F != -inf){
			if(st[id].mx != -1) st[id].ans = max(st[id].ans, abs(lz[id].F - st[id].mx));
			if(st[id].mn != -1) st[id].ans = max(st[id].ans, abs(lz[id].F - st[id].mn));
		}
		if(lz[id].S != inf){
			if(st[id].mx != -1) st[id].ans = max(st[id].ans, abs(lz[id].S - st[id].mx));
			if(st[id].mn != -1) st[id].ans = max(st[id].ans, abs(lz[id].S - st[id].mn));
		}
		if(l != r){
			lz[2 * id].F = max(lz[2 * id].F, lz[id].F); lz[2 * id].S = min(lz[2 * id].S, lz[id].S);
			lz[2 * id + 1].F = max(lz[2 * id + 1].F, lz[id].F); lz[2 * id + 1].S = min(lz[2 * id + 1].S, lz[id].S);
		}
		lz[id] = {-inf, inf};
	}
	void update_1(ll id, ll l, ll r, ll pos, ll val){
		down(id, l, r);
		if(l > pos || r < pos) return;
		if(l == r){
			st[id].mn = st[id].mx = val;
			return;
		}
		ll mid = (l + r) / 2;
		update_1(2 * id, l, mid, pos, val); update_1(2 * id + 1, mid + 1, r, pos, val);
		st[id] = merge(st[2 * id], st[2 * id + 1]);
	}
	
	void update_2(ll id, ll l, ll r, ll left, ll right, ll val){
		down(id, l, r);
		if(l > right || r < left) return;
		if(left <= l && r <= right){
			lz[id].F = max(lz[id].F, val); lz[id].S = min(lz[id].S, val);
			down(id, l, r);
			return;
		}
		ll mid = (l + r) / 2;
		update_2(2 * id, l, mid, left, right, val); update_2(2 * id + 1, mid + 1, r, left, right, val);
		st[id] = merge(st[2 * id], st[2 * id + 1]);
	}
	ll get(ll id, ll l, ll r, ll left, ll right){
		down(id, l, r);
		if(l > right || r < left) return -inf;
		if(left <= l && r <= right) return st[id].ans;
		ll mid = (l + r) / 2;
		return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
	}
	ll get(ll l, ll r){return get(1,1,n,l,r);}
	void update_1(ll pos, ll val){update_1(1,1,n,pos,val);}
	void update_2(ll l, ll r, ll val){update_2(1,1,n,l,r,val);}
} st;
void to_thic_cau(){
	cin >> n;
	for(int i = 1; i <= n;i++){
		cin >> h[i] >> a[i] >> b[i];
		ll l = i + a[i], r = i + b[i];
		if(l > r) continue;
		sweep[l].pb({i, h[i]});
		sweep[r + 1].pb({i, -1});
	}
	cin >> q;
	for(int i = 1; i <= q;i++){
		ll l,r; cin >> l >> r;
		t[r].pb({l, i});
	}
	st.init(n);
	for(int i = 1; i <= n;i++){
		for(auto x : sweep[i]){
			ll j = x.F, val = x.S;
			st.update_1(j, val);
		}
		ll l = max(1ll, i - b[i]), r = i - a[i];
		if(l <= r) st.update_2(l, r, h[i]);
		for(auto x : t[i]){
			res[x.S] = st.get(x.F, i);
		}
	}
	for(int i = 1; i <= q;i++){
		if(res[i] < 0) cout << -1 << '\n';
		else cout << res[i] << '\n';
	}
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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