Submission #613571

#	Time	Username	Problem	Language	Result	Execution time	Memory
613571		juggernaut	Two Antennas (JOI19_antennas)	C++14	35 / 100	266 ms	21656 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];
int tree[800005];
const int inf=1e9;
int ans=-1;
void chmax(int v,int l,int r,int ql,int qr,int val){
	if(ql<=l&&r<=qr){
		umax(tree[v],val);
		return;
	}
	if(qr<l||r<ql)return;
	int mid=(l+r)>>1;
	chmax(v<<1,l,mid,ql,qr,val);
	chmax(v<<1|1,mid+1,r,ql,qr,val);
}
void upd(int v,int l,int r,int pos,int val=-inf){
	umax(val,tree[v]);
	if(l==r){
		umax(ans,val-h[pos]);
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)upd(v<<1,l,mid,pos,val);
	else upd(v<<1|1,mid+1,r,pos,val);
}
void st(int v,int l,int r,int pos){
	if(l==r){
		tree[v]=-inf;
		return;
	}else{
		umax(tree[v<<1],tree[v]);
		umax(tree[v<<1|1],tree[v]);
	}
	tree[v]=-inf;
	int mid=(l+r)>>1;
	if(pos<=mid)st(v<<1,l,mid,pos);
	else st(v<<1|1,mid+1,r,pos);
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
	if(n<=2000){
		vector<vector<pair<int,int>>>query(n+1);
		int q;
		scanf("%d",&q);
		vector<int>ans(q,0),arr(n+1,-1);
		for(int i=0;i<q;i++){
			int l,r;
			scanf("%d%d",&l,&r);
			query[l].emplace_back(r,i);
		}
		for(int i=n;i>0;i--){
			for(int j=i+1;j<=n;j++){
				if(max(a[i],a[j])<=j-i&&j-i<=min(b[i],b[j])){
					umax(arr[j],abs(h[i]-h[j]));
				}
				umax(arr[j],arr[j-1]);
			}
			for(auto q:query[i])ans[q.sc]=arr[q.fr];
		}
		for(int i=0;i<q;i++)printf("%d\n",ans[i]);
	}else{
		{
			vector<vector<int>>inc(n+1),exc(n+1);
			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);
				if(i+a[i]<=n){
					chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
				}
				for(int idx:exc[i])upd(1,1,n,idx);
			}
		}
		reverse(h+1,h+1+n);
		reverse(a+1,a+1+n);
		reverse(b+1,b+1+n);
		memset(tree,0,sizeof tree);
		{
			vector<vector<int>>inc(n+1),exc(n+1);
			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);
				if(i+a[i]<=n){
					chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
				}
				for(int idx:exc[i])upd(1,1,n,idx);
			}
		}
		cout<<ans;
	}
}

Compilation message (stderr)

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

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