Submission #917349

#	Time	Username	Problem	Language	Result	Execution time	Memory
917349		amirhoseinfar1385	Two Antennas (JOI19_antennas)	C++17	100 / 100	403 ms	47812 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,q;
int h[maxn],a[maxn],b[maxn];
int kaf=(1<<19),inf=1e9+5;
vector<int>del[maxn],ins[maxn];
vector<pair<int,int>>allq[maxn];
int res[maxn];
struct segment{
	struct node{
		int r,mxq,mnq,mx,mn;
		node(){
			r=-1;
			mxq=mx=-inf;
			mn=mnq=inf;
		}
	};
	void calr(int i){
		seg[i].r=max(seg[i].r,seg[i].mxq-seg[i].mn);
		seg[i].r=max(seg[i].r,seg[i].mx-seg[i].mnq);
	}
	void calc(int i){
		calr(i);
		if(i>=kaf){
			return ;
		}
		seg[i].r=max(seg[i].r,max(seg[(i<<1)].r,seg[(i<<1)^1].r));
		seg[i].mx=max(seg[(i<<1)].mx,seg[(i<<1)^1].mx);
		seg[i].mn=min(seg[(i<<1)].mn,seg[(i<<1)^1].mn);
	}

	void shift(int i){
		if(i>=kaf){
			return ;
		}
		seg[(i<<1)].mxq=max(seg[(i<<1)].mxq,seg[i].mxq);
		seg[(i<<1)].mnq=min(seg[(i<<1)].mnq,seg[i].mnq);
		seg[(i<<1)^1].mxq=max(seg[(i<<1)^1].mxq,seg[i].mxq);
		seg[(i<<1)^1].mnq=min(seg[(i<<1)^1].mnq,seg[i].mnq);
		seg[i].mxq=-inf;
		seg[i].mnq=inf;
	}
	node seg[(1<<20)];
	void upd(int i,int l,int r,int tl,int tr,int mx,int mn){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			calr(i);
			seg[i].mxq=-inf;
			seg[i].mnq=inf;
			seg[i].mx=mx;
			seg[i].mn=mn;
			return ;
		}
		shift(i);
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,mx,mn);
		upd((i<<1)^1,m+1,r,tl,tr,mx,mn);
		calc(i);
		return ;
	}
	void qu(int i,int l,int r,int tl,int tr,int w){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].mnq=min(seg[i].mnq,w);
			seg[i].mxq=max(seg[i].mxq,w);
			calr(i);
			return ;
		}
		int m=(l+r)>>1;
		qu((i<<1),l,m,tl,tr,w);
		qu((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
	int pors(int i,int l,int r,int tl,int tr){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return -1;
		}
		if(l>=tl&&r<=tr){
			return seg[i].r;
		}
		shift(i);
		int m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));	
	}
}seg;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i]>>a[i]>>b[i];
		if(a[i]+i<maxn){
			ins[i+a[i]].push_back(i);
		}
		if(b[i]+i+1<maxn){
			del[b[i]+i+1].push_back(i);
		}
	}
	cin>>q;
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		allq[r].push_back(make_pair(l,i));
	}
	for(int i=1;i<=n;i++){
		for(auto x:del[i]){
			seg.upd(1,0,kaf-1,x,x,-inf,inf);
		}
		for(auto x:ins[i]){
			seg.upd(1,0,kaf-1,x,x,h[x],h[x]);
		}
		seg.qu(1,0,kaf-1,i-b[i],i-a[i],h[i]);
		for(auto x:allq[i]){
			res[x.second]=seg.pors(1,0,kaf-1,x.first,i);
		}
	}
	for(int i=0;i<q;i++){
		cout<<res[i]<<"\n";
	}
}

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