Submission #132045

#	Time	Username	Problem	Language	Result	Execution time	Memory
132045		hamzqq9	Two Antennas (JOI19_antennas)	C++14	35 / 100	2517 ms	479056 KiB

antennas

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 1000000000
#define N 200005
#define MOD 998244353
#define KOK 700		
using namespace std;

int n,q;
int h[N],a[N],b[N];
int ar[2][N/KOK+5][N];
int pos[N];
int beg[N/KOK+5],en[N/KOK+5];
vector<ii> Qmn[N],Qmx[N];

bool inter(int x,int y) {

	if(x>y) swap(x,y);

	if(y-b[y]<=x && y-a[y]>=x) {

		if(x+b[x]>=y && x+a[x]<=y) return 1;

	}

	return 0;

}

ii make(ii x) {

	umax(x.st,1);
	umin(x.nd,n);
	umax(x.nd,0);
	umin(x.st,n+1);

	return x;

}

vector<ii> get_seg(int x) {

	vector<ii> res;

	res.pb(make({x-b[x],x-a[x]}));
	res.pb(make({x+a[x],x+b[x]}));

	return res;

}

int solve(int x,int l,int r) {

	int res=-inf;

	if(r<1 || l>n) return res;

	if(pos[l]==pos[r]) {

		for(int i=l;i<=r;i++) {

			if(inter(x,i)) umax(res,abs(h[i]-h[x]));

		}

	}
	else {
		
		for(int i=l;i<=en[pos[l]];i++) {

			if(inter(x,i)) umax(res,abs(h[i]-h[x]));

		}

		for(int i=beg[pos[r]];i<=r;i++) {

			if(inter(x,i)) umax(res,abs(h[i]-h[x]));
			
		}

		l=pos[l]+1;
		r=pos[r]-1;

		for(int i=l;i<=r;i++) {

			int mn=ar[0][i][x];
			int mx=ar[1][i][x];

			umax(res,h[x]-mn);
			umax(res,mx-h[x]);

		}

	}

	return res;

}

int best(int x) {

	int res=-inf;

	vector<ii> seg=get_seg(x);

	for(auto y:seg) umax(res,solve(x,y.st,y.nd)); 

	return res;

}

void solvemn(int cur) {

	multiset<int> s;

	for(int i=1;i<=n;i++) {

		for(auto x:Qmn[i]) {

			if(x.nd==1) s.insert(x.st);
			else s.erase(s.find(x.st));

		}

		if(!sz(s)) ar[0][cur][i]=inf;
		else ar[0][cur][i]=*s.begin();

	}

}

void solvemx(int cur) {

	multiset<int> s;

	for(int i=1;i<=n;i++) {

		for(auto x:Qmx[i]) {

			if(x.nd==1) s.insert(x.st);
			else s.erase(s.find(x.st));

		}

		if(!sz(s)) ar[1][cur][i]=-inf;
		else ar[1][cur][i]=*s.rbegin();

	}

}

void create(int cur) {

	for(int i=1;i<=n;i++) {
	
		Qmx[i].clear();
		Qmn[i].clear();
	
	}

	for(int i=beg[cur];i<=en[cur];i++) {

		pos[i]=cur;

		vector<ii> seg=get_seg(i);

		for(auto x:seg) {

			Qmx[x.st].pb({h[i],1});
			Qmx[x.nd+1].pb({h[i],-1});
			Qmn[x.st].pb({h[i],1});
			Qmn[x.nd+1].pb({h[i],-1});

		}

	}	

	solvemx(cur);
	solvemn(cur);

}

void build() {

	for(int i=1;(beg[i]=(i-1)*KOK+1)<=n;i++) {

		en[i]=min(beg[i]+KOK-1,n);

		create(i);

	}

}

//-----------------------------------------------------------//

int dp[2005][2005];
bool vis[2005][2005];

int f(int i,int j) {

	if(i==j) return dp[i][j];

	if(vis[i][j]) return dp[i][j];

	vis[i][j]=1;

	return dp[i][j]=max(dp[i][j],max(f(i+1,j),f(i,j-1)));

}

void amele() {

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			dp[i][j]=-inf;

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=i;j<=n;j++) {

			if(inter(i,j)) {

				int cost=abs(h[i]-h[j]);

				umax(dp[i][j],cost);

			}

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=i;j<=n;j++) f(i,j);

	}

 	scanf("%d",&q);

	while(q--) {

		int l,r;

		scanf("%d %d",&l,&r);

		if(dp[l][r]<0) dp[l][r]=-1;

		printf("%d\n",dp[l][r]);

	}

	exit(0);

}

int main() {

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d %d %d",h+i,a+i,b+i);

	if(n<=2000) amele();
	
	scanf("%d",&q);

	assert(q==1);

	build();

	while(q--) {

		int l,r;

		scanf("%d %d",&l,&r);

		int cost=-inf;

		for(int i=l;i<=r;i++) {

			umax(cost,best(i));

		}

		printf("%d\n",cost);

	}

}

Compilation message (stderr)

antennas.cpp: In function 'void amele()':
antennas.cpp:256:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
antennas.cpp:262:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&l,&r);
   ~~~~~^~~~~~~~~~~~~~~
antennas.cpp: In function 'int main()':
antennas.cpp:276:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
antennas.cpp:278:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d %d %d",h+i,a+i,b+i);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:282:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
antennas.cpp:292:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&l,&r);
   ~~~~~^~~~~~~~~~~~~~~

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