Submission #158517

#	Time	Username	Problem	Language	Result	Execution time	Memory
158517		HungAnhGoldIBO2020	Two Antennas (JOI19_antennas)	C++14	100 / 100	1031 ms	40396 KiB

antennas

#include<bits/stdc++.h>
const int N=2e5+2;
const int inf=1e9+7;
using namespace std;
vector<int> que_lis[N];
vector<pair<int,bool> > event[N];
int c[4*N],d[4*N],lazy[4*N],ar[N],ans[N],ranl[N],ranr[N];
pair<int,int> que[N];
void init(int idx,int l,int r){
	c[idx]=-inf;
	d[idx]=-inf;
	lazy[idx]=-inf;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	init(idx<<1,l,mid);
	init(idx<<1|1,mid+1,r);
}
void push(int idx,int l,int r){
	lazy[idx<<1]=max(lazy[idx<<1],lazy[idx]);
	lazy[idx<<1|1]=max(lazy[idx<<1|1],lazy[idx]);
	d[idx<<1]=max(c[idx<<1]+lazy[idx<<1],d[idx<<1]);
	d[idx<<1|1]=max(c[idx<<1|1]+lazy[idx<<1|1],d[idx<<1|1]);
	lazy[idx]=-inf;	
}
void upd(int idx,int l,int r,int pos,bool haiz){
	if(l>pos||r<pos){
		return;	
	}	
	if(l==r){
		if(haiz){
			c[idx]=ar[pos];
		}
		else{
			d[idx]=max(d[idx],c[idx]+lazy[idx]);
			c[idx]=-inf;
		}
		lazy[idx]=-inf;
		return;
	}
	if(lazy[idx]!=-inf){
		push(idx,l,r);
	}
	int mid=(l+r)>>1;
	upd(idx<<1,l,mid,pos,haiz);
	upd(idx<<1|1,mid+1,r,pos,haiz);
	c[idx]=max(c[idx<<1],c[idx<<1|1]);
	d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1]));
}
void upd1(int idx,int l,int r,int lef,int rig,int val){
	if(l>rig||r<lef){
		return;
	}
	if(l>=lef&&r<=rig){
		lazy[idx]=max(lazy[idx],val);
		val=-inf;
		if(l!=r){
			val=max(d[idx<<1],d[idx<<1|1]);
		}
		d[idx]=max(max(c[idx]+lazy[idx],d[idx]),val);
		return;
	}
	if(lazy[idx]!=-inf){
		push(idx,l,r);
	}
	int mid=(l+r)>>1;
	upd1(idx<<1,l,mid,lef,rig,val);
	upd1(idx<<1|1,mid+1,r,lef,rig,val);
	d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1]));
}
int getmax(int idx,int l,int r,int lef,int rig){
	if(l>rig||r<lef){
		return -inf;
	}
	if(l>=lef&&r<=rig){
		return d[idx];
	}
	if(lazy[idx]!=-inf){
		push(idx,l,r);
	}
	int mid=(l+r)>>1;
	return max(getmax(idx<<1,l,mid,lef,rig),getmax(idx<<1|1,mid+1,r,lef,rig));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,q;
	cin>>n;
	init(1,1,n);
	for(i=1;i<=n;i++){
		cin>>ar[i]>>ranl[i]>>ranr[i];
		ranr[i]++;
		if(i+ranl[i]<=n){
			event[i+ranl[i]].push_back({i,true});
		}
		if(i+ranr[i]<=n){
			event[i+ranr[i]].push_back({i,false});
		}
	}
	cin>>q;
	for(i=1;i<=q;i++){
		ans[i]=-1;
		cin>>que[i].first>>que[i].second;
		que_lis[que[i].second].push_back(i);
	}
	for(i=1;i<=n;i++){
		for(j=0;j<event[i].size();j++){
			upd(1,1,n,event[i][j].first,event[i][j].second);
		}
		if(i-ranl[i]>0){
			upd1(1,1,n,max(1,i-ranr[i]+1),i-ranl[i],-ar[i]);
		}
		for(j=0;j<que_lis[i].size();j++){
//			cout<<que_lis[i][j]<<' '<<getmax(1,1,n,que[que_lis[i][j]].first,i)<<endl;
			ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,que[que_lis[i][j]].first,i));
		}
		event[i].clear();
		que_lis[i].clear();
	}
	init(1,1,n);
	for(i=n;i>=1;i--){
		if(i-ranl[i]>0){
			event[i-ranl[i]].push_back({i,true});
		}
		if(i-ranr[i]>0){
			event[i-ranr[i]].push_back({i,false});
		}
	}
	for(i=1;i<=q;i++){
		que_lis[que[i].first].push_back(i);
	}
	for(i=n;i>=1;i--){
		for(j=0;j<event[i].size();j++){
			upd(1,1,n,event[i][j].first,event[i][j].second);
		}
		if(i+ranl[i]<=n){
			upd1(1,1,n,i+ranl[i],min(i+ranr[i]-1,n),-ar[i]);
		}
		for(j=0;j<que_lis[i].size();j++){
			ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,i,que[que_lis[i][j]].second));
		}
	}
	for(i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
*/

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<event[i].size();j++){
           ~^~~~~~~~~~~~~~~~
antennas.cpp:114:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<que_lis[i].size();j++){
           ~^~~~~~~~~~~~~~~~~~
antennas.cpp:134:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<event[i].size();j++){
           ~^~~~~~~~~~~~~~~~
antennas.cpp:140:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<que_lis[i].size();j++){
           ~^~~~~~~~~~~~~~~~~~
antennas.cpp:88:12: warning: unused variable 'k' [-Wunused-variable]
  int n,i,j,k,l,q;
            ^
antennas.cpp:88:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,q;
              ^

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