Submission #384738

#	Time	Username	Problem	Language	Result	Execution time	Memory
384738		ogibogi2004	Two Antennas (JOI19_antennas)	C++14	0 / 100	596 ms	28032 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=2e9;
ll h[MAXN],a[MAXN],b[MAXN];
struct event
{
	int f;
	/*
	2-ask
	1-add
	0-remove
	*/
	int idx;
	int x;
	bool operator<(event const& other)const
	{
		if(x!=other.x)return x<other.x;
		return other.f==0;
	}
};
struct segment_tree
{
	ll treemin[4*MAXN],treemax[4*MAXN];
	void init()
	{
		for(int i=1;i<4*MAXN;i++)
		{
			treemin[i]=INF;
			treemax[i]=-INF;
		}
	}
	void update(int l,int r,int idx,int q,int val)
	{
		if(l>q)return;
		if(r<q)return;
		if(l==r)
		{
			if(val==0)
			{
				treemin[idx]=INF;
				treemax[idx]=-INF;
			}
			else 
			{
				treemin[idx]=val;
				treemax[idx]=val;
			}
			return;
		}
		int mid=(l+r)/2;
		update(l,mid,idx*2,q,val);
		update(mid+1,r,idx*2+1,q,val);
		treemax[idx]=max(treemax[idx*2],treemax[idx*2+1]);
		treemin[idx]=min(treemin[idx*2],treemin[idx*2+1]);
	}
	void update(int q,int val)
	{
		update(1,MAXN,1,q,val);
	}
	ll querymin(int l,int r,int ql,int qr,int idx)
	{
		if(l>qr)return INF;
		if(r<ql)return INF;
		if(l>=ql&&r<=qr)return treemin[idx];
		int mid=(l+r)/2;
		return min(querymin(l,mid,ql,qr,idx*2),querymin(mid+1,r,ql,qr,idx*2+1));
	}
	ll querymin(ll l,ll r)
	{
		if(r<=0||l>MAXN)return INF;
		return querymin(1,MAXN,max(1ll,l),min(MAXN,r),1);
	}
	ll querymax(int l,int r,int ql,int qr,int idx)
	{
		if(l>qr)return -INF;
		if(r<ql)return -INF;
		if(l>=ql&&r<=qr)return treemax[idx];
		int mid=(l+r)/2;
		return max(querymax(l,mid,ql,qr,idx*2),querymax(mid+1,r,ql,qr,idx*2+1));
	}
	ll querymax(ll l,ll r)
	{
		if(r<=0||l>MAXN)return -INF;
		return querymax(1,MAXN,max(1ll,l),min(MAXN,r),1);
	}
}t;
vector<event>e;
int n,q;
int main()
{
	t.init();
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i]>>a[i]>>b[i];
		e.push_back({2,i,i});
		e.push_back({1,i,i-b[i]});
		e.push_back({0,i,i-a[i]});
		e.push_back({1,i,i+a[i]});
		e.push_back({0,i,i+b[i]});
	}
	sort(e.begin(),e.end());
	cin>>q;
	cin>>q;
	cin>>q;
	ll ans=-INF;
	for(int i=0;i<e.size();i++)
	{
		if(e[i].f==2)
		{
			ll h1=max(t.querymax(i-b[e[i].idx],i-a[e[i].idx]),t.querymax(i+a[e[i].idx],i+b[e[i].idx]));
			ll h2=min(t.querymin(i-b[e[i].idx],i-a[e[i].idx]),t.querymin(i+a[e[i].idx],i+b[e[i].idx]));
			//cout<<e[i].idx<<" "<<h1-h[e[i].idx]<<" "<<h[e[i].idx]-h2<<" "<<h1<<" "<<h2<<endl;
			ans=max(ans,h1-h[e[i].idx]);
			ans=max(ans,h[e[i].idx]-h2);
		}
		else if(e[i].f==0)
		{
			t.update(e[i].idx,0);
		}
		else
		{
			t.update(e[i].idx,h[e[i].idx]);
		}
	}
	if(ans<=0)
	{
		cout<<"-1\n";
		return 0;
	}
	cout<<ans<<endl;
return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:99:21: warning: narrowing conversion of '(((long long int)i) - b[i])' from 'long long int' to 'int' [-Wnarrowing]
   99 |   e.push_back({1,i,i-b[i]});
      |                    ~^~~~~
antennas.cpp:100:21: warning: narrowing conversion of '(((long long int)i) - a[i])' from 'long long int' to 'int' [-Wnarrowing]
  100 |   e.push_back({0,i,i-a[i]});
      |                    ~^~~~~
antennas.cpp:101:21: warning: narrowing conversion of '(((long long int)i) + a[i])' from 'long long int' to 'int' [-Wnarrowing]
  101 |   e.push_back({1,i,i+a[i]});
      |                    ~^~~~~
antennas.cpp:102:21: warning: narrowing conversion of '(((long long int)i) + b[i])' from 'long long int' to 'int' [-Wnarrowing]
  102 |   e.push_back({0,i,i+b[i]});
      |                    ~^~~~~
antennas.cpp:109:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for(int i=0;i<e.size();i++)
      |              ~^~~~~~~~~

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