Submission #385167

#	Time	Username	Problem	Language	Result	Execution time	Memory
385167		ogibogi2004	Two Antennas (JOI19_antennas)	C++14	0 / 100	859 ms	42016 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define remove adsfdsfdsf
const ll MAXN=2e5+6;
const ll INF=2e12;
ll n,q,h[MAXN],a[MAXN],b[MAXN];
ll ans[MAXN];
vector<ll>add[MAXN];
vector<ll>remove[MAXN];
vector<pair<ll,ll> >queries[MAXN];
struct segment_tree
{
	struct node
	{
		ll this_val;
		ll max_other;
		ll max_dif;
	};
	node tree[4*MAXN];
	void init()
	{
		for(ll i=0;i<4*MAXN;i++)
		{
			tree[i].this_val=INF;
			tree[i].max_other=-INF;
			tree[i].max_dif=-INF;
		}
	}
	void recalc(ll idx)
	{
		tree[idx].max_dif=max(tree[idx].max_dif,tree[idx].max_other-tree[idx].this_val);
	}
	/*void recalc(node &t)
	{
		t.max_dif=max(t.max_dif,t.max_other-t.this_val);
	}*/
	void push(ll idx)
	{
		recalc(idx);
		recalc(idx*2);
		tree[idx*2].max_other=max(tree[idx*2].max_other,tree[idx].max_other);
		recalc(idx*2);
		recalc(idx*2+1);
		tree[idx*2+1].max_other=max(tree[idx*2+1].max_other,tree[idx].max_other);
		recalc(idx*2+1);
		recalc(idx);
	}
	node merge(ll idx1,ll idx2)
	{
		//push(idx1/2);
		recalc(idx1);
		recalc(idx2);
		node ret;
		ret.this_val=INF;
		ret.max_other=-INF;
		ret.max_dif=max(tree[idx1].max_dif,tree[idx2].max_dif);
		return ret;
	}
	void push(ll l,ll r,ll idx)
	{
		recalc(idx);
		if(l!=r)
		{
			recalc(idx*2);
			tree[idx*2].max_other=max(tree[idx*2].max_other,tree[idx].max_other);
			recalc(idx*2);
			recalc(idx*2+1);
			tree[idx*2+1].max_other=max(tree[idx*2+1].max_other,tree[idx].max_other);
			recalc(idx*2+1);
		}
		recalc(idx);
		if(l!=r)tree[idx]=merge(idx*2,idx*2+1);
	}
	void update_this(ll l,ll r,ll idx,ll q,ll val)
	{
		push(l,r,idx);
		if(l>q)return;
		if(r<q)return;
		if(l==r)
		{
			recalc(idx);
			tree[idx].this_val=val;
			tree[idx].max_other=-INF;
			recalc(idx);
			return;
		}
		ll mid=(l+r)/2;
		update_this(l,mid,idx*2,q,val);
		update_this(mid+1,r,idx*2+1,q,val);
		tree[idx]=merge(idx*2,idx*2+1);
	}
	void update_this(ll q,ll val)
	{
		update_this(1,n,1,q,val);
	}
	void update_range(ll l,ll r,ll idx,ll ql,ll qr,ll val)
	{
		push(l,r,idx);
		if(l>qr||r<ql)return;
		recalc(idx);
		if(l>=ql&&r<=qr)
		{
			tree[idx].max_other=max(tree[idx].max_other,val);
			push(l,r,idx);
			return;
		}
		ll mid=(l+r)/2;
		update_range(l,mid,idx*2,ql,qr,val);
		update_range(mid+1,r,idx*2+1,ql,qr,val);
		tree[idx]=merge(idx*2,idx*2+1);
	}
	void update_range(ll ql,ll qr,ll val)
	{
		update_range(1,n,1,ql,qr,val);
	}
	ll query(ll l,ll r,ll idx,ll ql,ll qr)
	{
		push(l,r,idx);
		//cout<<l<<" "<<r<<" "<<idx<<endl;
		if(l>qr||r<ql)return -INF;
		if(l>=ql&&r<=qr)
		{
			//cout<<l<<" "<<r<<" "<<idx<<" "<<tree[idx].max_dif<<endl;
			return tree[idx].max_dif;
		}
		ll mid=(l+r)/2;
		return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
	ll query(ll ql,ll qr)
	{
		return query(1,n,1,ql,qr);
	}
	void print(ll l,ll r,ll idx)
	{
		cout<<l<<" "<<r<<" "<<idx<<":\n";
		cout<<tree[idx].this_val<<" "<<tree[idx].max_other<<" "<<tree[idx].max_dif<<endl;
		if(l!=r)print(l,(l+r)/2,idx*2);
		if(l!=r)print((l+r)/2+1,r,idx*2+1);
	}
}t;
void solve()
{
	t.init();
	for(ll i=1;i<=n;i++)
	{
		/*cout<<"----------------";
		cout<<"\n";
		cout<<"     "<<i<<"\n";
		cout<<"\n";*/
		for(auto xd:add[i])
		{
			//cout<<"add1 "<<xd<<endl;
			t.update_this(xd,h[xd]);
		}
		ll l=i-b[i];
		ll r=i-a[i];
		l=max(1ll,l);
		if(l<=r)
		{
			//cout<<"add2 "<<i<<" "<<l<<" "<<r<<endl;
			t.update_range(l,r,h[i]);
		}
		//t.print(1,n,1);
		/*for(int j=1;j<=i;j++)
		{
			cout<<"query "<<j<<" "<<i<<" "<<t.query(j,i)<<endl;
		}
		for(int j=1;j<i;j++)
		{
			cout<<"query "<<j<<" "<<i-1<<" "<<t.query(j,i-1)<<endl;
		}*/
		for(auto xd:queries[i])
		{
			//cout<<"query "<<xd.first<<" "<<i<<endl;
			ans[xd.second]=max(ans[xd.second],t.query(xd.first,i));
		}
		for(auto xd:remove[i])
		{
			//cout<<"remove1 "<<xd<<endl;
			t.update_this(xd,INF);
		}
		//t.print(1,n,1);
	}
}
void read()
{
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>h[i]>>a[i]>>b[i];
	}
	cin>>q;
	for(ll i=1;i<=q;i++)
	{
		ll l,r;
		cin>>l>>r;
		ans[i]=-1;
		queries[r].push_back({l,i});
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	for(ll i=1;i<=n;i++)
	{
		if(i+a[i]>n)continue;
		remove[min(n,i+b[i])].push_back(i);
		add[i+a[i]].push_back(i);
	}
	solve();
	for(ll i=1;i<=n;i++)h[i]=-h[i];
	/*for(ll i=1;i<=q;i++)
	{
		cout<<ans[i]<<endl;
	}*/
	solve();
	for(ll i=1;i<=q;i++)
	{
		cout<<ans[i]<<endl;
	}
return 0;
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
*/

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