Submission #136417

#	Time	Username	Problem	Language	Result	Execution time	Memory
136417		scanhex	Two Antennas (JOI19_antennas)	C++17	100 / 100	1079 ms	46856 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
#define sz(x) int((x).size())

const int LG=18;
const int N=1<<LG;
const int oo=0x3f3f3f3f;
struct it{
	int t[2*N],ans[2*N],mnh[2*N],psh[2*N];
	void init(){
		fill(t,t+2*N,0);
		fill(psh,psh+2*N,0);
		fill(ans,ans+2*N,-oo);
		fill(mnh,mnh+2*N,oo);
	}
	it(){
		init();
	}
	void app(int x,int y){
		ans[x]=max(ans[x],y-mnh[x]);
		t[x]=max(t[x],y);
		psh[x]=max(psh[x],y);
	}
	void push1(int x){
		app(2*x,psh[x]);
		app(2*x+1,psh[x]);
		psh[x]=0;
	}
	void push(int x){
		 for(int i=LG;i;--i)
			 push1(x>>i);
	}
	void upd(int x){
		while(x>1){
			t[x>>1]=max(t[x],t[x^1]);
			ans[x>>1]=max(ans[x],ans[x^1]);
			x>>=1;
		}
	}
	void chh(int x,int y){
		x+=N;
		push(x);
		ans[x]=max(ans[x],t[x]-y);
		mnh[x]=y;
		upd(x);
		while(x>1)mnh[x>>1]=min(mnh[x],mnh[x^1]),x>>=1;
	}
	void chan(int l,int r,int v){
		if(r<=l)return;
		l+=N;
		r+=N;
		int l1=l,r1=r;
		push(l);
		push(r-1);
		while(l<r){
			if(l&1)
				app(l++,v);
			if(r&1)
				app(--r,v);
			l>>=1,r>>=1;
		}
		push(l1);
		push(r1-1);
		upd(l1);
		upd(r1-1);
	}
	int get(int l,int r){
		l+=N;
		r+=N;
		int ans=-1;
		push(l);
		push(r-1);
		while(l<r){
			if(l&1)ans=max(ans,this->ans[l++]);
			if(r&1)ans=max(ans,this->ans[--r]);
			l/=2,r/=2;
		}
		return ans;
	}
} myit;
int n,q;
int a[N],b[N];
int h[N];
int ans[N];
pair<int,int>qs[N];
vector<pair<int,int>>mts[N];
vector<int>evs[N];
int stup(int l,int r){
	int ans=-1;
	for(int i=l;i<=r;++i)
		for(int j=i+1;j<=r;++j)
			if(a[i]<=j-i&&j-i<=b[i]&&a[j]<=j-i&&j-i<=b[j])
				ans=max(ans,h[j]-h[i]);
	return ans;
}
void solve(){
	for(int i=0;i<n;++i)mts[i].clear();
	for(int i=0;i<q;++i)mts[qs[i].second].emplace_back(qs[i].first,i);
	myit.init();
	for(int i=0;i<n;++i)evs[i].clear();
	for(int i=0;i<n;++i){
		evs[min(i+a[i],n)].push_back(i);
		evs[min(i+b[i]+1,n)].push_back(i);
	}
	vector<bool>u(n);
	for(int i=0;i<n;++i){
		for(int x:evs[i]){
			if(!u[x]){
				myit.push(N+x);
				myit.t[N+x]=0;
				myit.upd(N+x);
				myit.chh(x,h[x]),u[x]=1;
			}
			else
				myit.chh(x,oo);
		}
		int l=max(0,i-b[i]);
		int r=max(0,i-a[i]+1);
		myit.chan(l,r,h[i]);
		for(auto&[l,ind]:mts[i]){
			int kek=myit.get(l,i+1);
//			cerr<<kek<<' '<<stup(l,i)<<'\n';
//			assert(kek==stup(l,i));
			ans[ind]=max(ans[ind],kek);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;++i)cin>>h[i]>>a[i]>>b[i];
	cin>>q;
	fill(ans,ans+q,-1);
	for(int i=0;i<q;++i){
		int a,b;
		cin>>a>>b;
		--a;
		--b;
		qs[i]={a,b};
	}
	solve();
	reverse(h,h+n);
	reverse(a,a+n);
	reverse(b,b+n);
	for(int i=0;i<q;++i){
		qs[i].second=n-qs[i].second-1;
		qs[i].first=n-qs[i].first-1;
		swap(qs[i].first,qs[i].second);
	}
	solve();
	for(int i=0;i<q;++i)
		cout<<ans[i]<<'\n';
	return 0;
}

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