Submission #391233

#	Time	Username	Problem	Language	Result	Execution time	Memory
391233		kshitij_sodani	Two Antennas (JOI19_antennas)	C++14	100 / 100	1137 ms	50932 KiB

antennas

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n,q;
llo it[200001];
llo aa[200001];
llo bb[200001];

llo tree[4*200001];
llo tree2[4*200001];
llo lazy[4*200001];
vector<pair<llo,llo>> pre[200001];
vector<llo> pre2[200001];
vector<llo> pre3[200001];
llo ans[200001];
void push(llo no,llo l,llo r){
	tree2[no]=max(tree2[no],tree[no]-lazy[no]);
	/*if(tree[no]==10 and lazy[no]==1){
		cout<<no<<"."<<l<<"."<<r<<endl;
	}*/
	if(l<r){
		lazy[no*2+1]=min(lazy[no*2+1],lazy[no]);
		lazy[no*2+2]=min(lazy[no*2+2],lazy[no]);
	}
	lazy[no]=(llo)1e18;
}
void update(llo no,llo l,llo r,llo i,llo val){
	push(no,l,r);
	if(l==r){
		tree[no]=val;
	//	lazy[no]=(llo)1e18;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,val);
			push(no*2+2,mid+1,r);
		}
		else{
			update(no*2+2,mid+1,r,i,val);
			push(no*2+1,l,mid);
		}
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);

	}
}
void update2(llo no,llo l,llo r,llo aa,llo bb,llo val){
	push(no,l,r);
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]=min(lazy[no],val);
		push(no,l,r);
	}
	else{
		llo mid=(l+r)/2;
		update2(no*2+1,l,mid,aa,bb,val);
		update2(no*2+2,mid+1,r,aa,bb,val);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	push(no,l,r);
	if(r<aa or l>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree2[no];
	}
	else{
		llo mid=(l+r)/2;
		llo x=query(no*2+1,l,mid,aa,bb);
		llo y=query(no*2+2,mid+1,r,aa,bb);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
		return max(x,y);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i]>>aa[i]>>bb[i];
		it[i]=-it[i];
		if(i+aa[i]<n){
			pre2[i+aa[i]].pb(i);
		}
		if(i+bb[i]<n){
			pre3[i+bb[i]].pb(i);
		}
	}
	cin>>q;
	for(llo i=0;i<q;i++){
		llo l,r;
		cin>>l>>r;
		l--;
		r--;
		pre[r].pb({l,i});
		ans[i]=-1;
	}

	for(llo i=0;i<4*n;i++){
		tree[i]=-(llo)1e18;
		tree2[i]=-1;
		lazy[i]=(llo)1e18;
	}
	for(llo i=0;i<n;i++){
		for(auto j:pre2[i]){
			//cout<<i<<":"<<j<<endl;
			update(0,0,n-1,j,it[j]);
		}
		if(i-aa[i]>=0){
			//cout<<max(i-bb[i],(llo)0)<<"<"<<i-aa[i]<<"<"<<it[i]<<endl;
			update2(0,0,n-1,max(i-bb[i],(llo)0),i-aa[i],it[i]);
		}
		//cout<<query(0,0,n-1,0,n-1)<<endl;
		for(auto j:pre[i]){
			ans[j.b]=query(0,0,n-1,j.a,i);
		}
		for(auto j:pre3[i]){
			//cout<<i<<",,"<<j<<endl;
			update(0,0,n-1,j,-(llo)1e18);
		}
	}
	for(int i=0;i<n;i++){
		it[i]=-it[i];
	}
	for(llo i=0;i<4*n;i++){
		tree[i]=-(llo)1e18;
		tree2[i]=-1;
		lazy[i]=(llo)1e18;
	}
	for(llo i=0;i<n;i++){
		for(auto j:pre2[i]){
			//cout<<i<<":"<<j<<endl;
			update(0,0,n-1,j,it[j]);
		}
		if(i-aa[i]>=0){
			//cout<<max(i-bb[i],(llo)0)<<"<"<<i-aa[i]<<"<"<<it[i]<<endl;
			update2(0,0,n-1,max(i-bb[i],(llo)0),i-aa[i],it[i]);
		}
		//cout<<query(0,0,n-1,0,n-1)<<endl;
		for(auto j:pre[i]){
			ans[j.b]=max(ans[j.b],query(0,0,n-1,j.a,i));
		}
		for(auto j:pre3[i]){
			//cout<<i<<",,"<<j<<endl;
			update(0,0,n-1,j,-(llo)1e18);
		}
	}
	for(llo i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}






 
 
	return 0;
}
 

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