Submission #613625

#	Time	Username	Problem	Language	Result	Execution time	Memory
613625		juggernaut	Two Antennas (JOI19_antennas)	C++14	13 / 100	3084 ms	20572 KiB

antennas

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int h[200005];
int a[200005];
int b[200005];
const int inf=1e9;
int ans[200005];
int n;
vector<pair<int,int>>queries;
int q;
int lz[800005];
pair<int,int>tree[800005];
/*void build(int v,int l,int r){
	if(l==r){
		lz[v]=0;
		tree[v]={-inf,0};
		return;
	}
	int mid=(l+r)>>1;
	build(v<<1,l,mid);
	build(v<<1|1,mid+1,r);
	tree[v]=max(tree[v<<1],tree[v<<1|1]);
}
void push(int &v,int &l,int &r){
	if(l^r){
		umax(lz[v<<1],lz[v]);
		umax(lz[v<<1|1],lz[v]);
	}
	lz[v]=0;
}
void st(int v,int l,int r,int pos,int val,int mx=0){
	umax(mx,lz[v]);
	if(l==r){
		tree[v]={mx-val,-mx};
		lz[v]=0;
		return;
	}else{
		umax(lz[v<<1],lz[v]);
		umax(lz[v<<1|1],lz[v]);
	}
	int mid=(l+r)>>1;
	if(pos<=mid)st(v<<1,l,mid,pos,val,mx);
	else st(v<<1|1,mid+1,r,pos,val,mx);
	tree[v]=max(tree[v<<1],tree[v<<1|1]);
}
void chmax(int v,int l,int r,int ql,int qr,int val){
	if(qr<l||r<ql)return;
	if(ql<=l&&r<=qr){
		umax(lz[v],val);
		if(-tree[v].sc<lz[v]){
			int pivot=lz[v]+tree[v].sc;
			tree[v].sc-=pivot;
			tree[v].fr+=pivot;
		}
		return;
	}
	int mid=(l+r)>>1;
	chmax(v<<1,l,mid,ql,qr,val);
	chmax(v<<1|1,mid+1,r,ql,qr,val);
	tree[v]=max(tree[v<<1],tree[v<<1|1]);
}
int get(int v,int l,int r,int ql,int qr){
	if(qr<l||r<ql)return -1;
	if(ql<=l&&r<=qr)return tree[v].fr;
	int mid=(l+r)>>1;
	return max(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid+1,r,ql,qr));
}*/
int x[200005];
int y[200005];
int best[200005];
void build(int v,int l,int r){
	for(int i=l;i<=r;i++){
		x[i]=0;
		y[i]=inf;
		best[i]=-inf;
	}
}
void st(int v,int l,int r,int pos,int val){
	y[pos]=val;
	x[pos]=0;
	umax(best[pos],-val);
}
void chmax(int v,int l,int r,int ql,int qr,int val){
	for(int i=ql;i<=qr;i++){
		umax(x[i],val);
		umax(best[i],x[i]-y[i]);
	}
}
int get(int v,int l,int r,int ql,int qr){
	int ans=-1;
	for(int i=ql;i<=qr;i++)umax(ans,best[i]);
	return ans;
}
void solve(){
	build(1,1,n);
	vector<vector<int>>inc(n+1),exc(n+1),query(n+1);
	for(int i=0;i<q;i++)query[queries[i].fr].push_back(i);
	for(int i=1;i<=n;i++){
		if(i>a[i]){
			exc[max(1,i-b[i])].push_back(i);
			inc[i-a[i]].push_back(i);
		}
	}
	for(int i=n;i;i--){
		for(int idx:inc[i])st(1,1,n,idx,h[idx]);
		if(i+a[i]<=n)
			chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
		for(int idx:query[i])
			umax(ans[idx],get(1,1,n,i,queries[idx].sc));
		for(int idx:exc[i])st(1,1,n,idx,inf);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
	scanf("%d",&q);
	for(int i=0;i^q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		queries.emplace_back(l,r);
		ans[i]=-1;
	}
	solve();
	reverse(h+1,h+1+n);
	reverse(a+1,a+1+n);
	reverse(b+1,b+1+n);
	for(auto &to:queries)to=make_pair(n-to.sc+1,n-to.fr+1);
	solve();
	for(int i=0;i<q;i++)printf("%d\n",ans[i]);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
antennas.cpp:126:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
antennas.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~

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