Submission #111207

#	Time	Username	Problem	Language	Result	Execution time	Memory
111207		zscoder	Two Antennas (JOI19_antennas)	C++17	100 / 100	1207 ms	63540 KiB

antennas

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int h[255555];
int a[255555];
int b[255555];
int ans[255555];
vector<ii> Q[255555];
const int INF = int(2e9)+20;

struct node
{
	int mx;
	int minc;
	int lazyx;
	node(int _mx=-INF,int _minc=INF,int _lazyx=-INF):mx(_mx),minc(_minc),lazyx(_lazyx){};
};

node st[255555*4];

void reset()
{
	for(int i=0;i<255555*4;i++) st[i]=node();
}

void combine(int id)
{
	st[id].mx=max(st[id*2].mx,st[id*2+1].mx);
	st[id].minc=min(st[id*2].minc,st[id*2+1].minc);
}

void push(int id, int l, int r)
{
	if(st[id].lazyx!=-INF)
	{
		st[id].mx=max(st[id].mx,st[id].lazyx-st[id].minc);
		if(r-l>=2)
		{
			st[id*2].lazyx=max(st[id*2].lazyx,st[id].lazyx);
			st[id*2+1].lazyx=max(st[id*2+1].lazyx,st[id].lazyx);
		}
		st[id].lazyx=-INF;
	}
}

void update(int id, int l, int r, int pos, int newc)
{
	push(id,l,r);
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[id].minc=newc;
		return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,newc); update(id*2+1,mid,r,pos,newc);
	combine(id);
}

void amax(int id, int l, int r, int ql, int qr, int v)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		st[id].lazyx=v;
		push(id,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	amax(id*2,l,mid,ql,qr,v); amax(id*2+1,mid,r,ql,qr,v);
	combine(id);
}

int query(int id, int l, int r, int ql, int qr)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return -INF;
	if(ql<=l&&r<=qr) return st[id].mx;
	int mid=(l+r)>>1;
	return max(query(id*2,l,mid,ql,qr),query(id*2+1,mid,r,ql,qr));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); 
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>h[i]>>a[i]>>b[i];
	}
	int q; cin>>q;
	vector<pair<ii,int> > queries;
	for(int i=0;i<q;i++)
	{
		int l,r; cin>>l>>r; l--; r--;
		queries.pb({{l,r},i});
		ans[i]=-1;
	}
	for(int loop=0;loop<2;loop++)
	{
		for(int i=0;i<n;i++) Q[i].clear();
		for(int i=0;i<q;i++)
		{
			Q[queries[i].fi.se].pb(mp(queries[i].fi.fi,i));
		}
		vector<pair<int,ii> > events;
		for(int i=0;i<n;i++)
		{
			events.pb(mp(i+a[i],mp(i,1)));
			events.pb(mp(i+b[i]+1,mp(i,-1)));
		}
		int ptr=0;
		reset();
		sort(events.begin(),events.end());
		for(int i=0;i<n;i++)
		{
			int L=i-b[i]; int R=i-a[i];
			L=max(L,0); R=max(R,-1);
			while(ptr<events.size()&&events[ptr].fi<=i)
			{
				if(events[ptr].se.se==-1)
				{
					update(1,0,n,events[ptr].se.fi,INF);
				}
				else
				{
					update(1,0,n,events[ptr].se.fi,h[events[ptr].se.fi]);
				}
				ptr++;
			}
			amax(1,0,n,L,R+1,h[i]);
			for(ii v:Q[i])
			{
				ans[v.se]=max(ans[v.se],query(1,0,n,v.fi,i+1));
			}
		}
		reverse(h,h+n);
		reverse(a,a+n);
		reverse(b,b+n);
		for(int i=0;i<queries.size();i++)
		{
			queries[i].fi.fi=n-1-queries[i].fi.fi;
			queries[i].fi.se=n-1-queries[i].fi.se;
			swap(queries[i].fi.fi,queries[i].fi.se);
		}
	}
	for(int i=0;i<q;i++)
	{
		cout<<ans[i]<<'\n';
	}
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:138:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ptr<events.size()&&events[ptr].fi<=i)
          ~~~^~~~~~~~~~~~~~
antennas.cpp:159:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<queries.size();i++)
               ~^~~~~~~~~~~~~~~

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