Submission #1266729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266729		namhh	Two Antennas (JOI19_antennas)	C++20	0 / 100	154 ms	41292 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,q,h[N],a[N],b[N],ans[N];
pii lazy[4*N];
struct Node{
	int mx,mn,mxval;
};
Node st[4*N];
Node merge(Node a, Node b){
	Node c;
	c.mx = max(a.mx,b.mx);
	c.mn = min(a.mn,b.mn);
	c.mxval = max(a.mxval,b.mxval);
	return c;
}
void build(int id, int l, int r){
	if(l == r){
		st[id] = {(int)-1e18,(int)1e18,(int)-1e18};
		return;
	}
	int mid = (l+r)/2;
	build(2*id,l,mid);
	build(2*id+1,mid+1,r);
	st[id] = merge(st[2*id],st[2*id+1]);
}
void update(int id, int l, int r, int i, int val1, int val2){
	if(l > i || r < i) return;
	if(l == r){
		st[id].mx = val1;
		st[id].mn = val2;
		return;
	}
	int mid = (l+r)/2;
	update(2*id,l,mid,i,val1,val2);
	update(2*id+1,mid+1,r,i,val1,val2);
	st[id] = merge(st[2*id],st[2*id+1]);
}
void down(int id){
	lazy[2*id].fi = max(lazy[2*id].fi,lazy[id].fi);
	lazy[2*id+1].fi = max(lazy[2*id+1].fi,lazy[id].fi);
	lazy[2*id].se = min(lazy[2*id].se,lazy[id].se);
	lazy[2*id+1].se = min(lazy[2*id+1].se,lazy[id].se);
	st[2*id].mxval = max({st[2*id].mxval,st[2*id].mx-lazy[id].se,lazy[id].fi-st[2*id].mn});
	st[2*id+1].mxval = max({st[2*id+1].mxval,st[2*id+1].mx-lazy[id].se,lazy[id].fi-st[2*id+1].mn});
	lazy[id] = {-1e18,1e18};
}
void update1(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		lazy[id].fi = max(lazy[id].fi,val);
		lazy[id].se = min(lazy[id].se,val);
		st[id].mxval = max({st[id].mxval,st[id].mx-lazy[id].fi,lazy[id].se-st[id].mn});
		return;
	}
	if(l != r) down(id);
	int mid = (l+r)/2;
	update1(2*id,l,mid,u,v,val);
	update1(2*id+1,mid+1,r,u,v,val);
	st[id] = merge(st[2*id],st[2*id+1]);
}
Node get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return {(int)-1e18,(int)1e18,(int)-1e18};
	if(l != r) down(id);
	if(l >= u && r <= v) return st[id];
	int mid = (l+r)/2;
	return merge(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
vector<pii>events[N],query[N];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> h[i] >> a[i] >> b[i];
		if(i+a[i] <= n) events[i+a[i]].push_back({i,1});
		if(i+b[i]+1 <= n) events[i+b[i]+1].push_back({i,-1});
	}
	build(1,1,n);
	for(int i = 1; i <= 4*n; i++) lazy[i].se = 1e18;
	cin >> q;
	for(int i = 1; i <= q; i++){
		int l,r;
		cin >> l >> r;
		query[r].push_back({l,i});
	}
	for(int i = 1; i <= n; i++){
		for(auto v: events[i]){
			if(v.se == 1) update(1,1,n,v.fi,h[v.fi],h[v.fi]);
			else update(1,1,n,v.fi,-1e18,1e18);
		}
		int l = max((int)1,i-b[i]);
		int r = i-a[i];
		if(l <= r) update1(1,1,n,l,r,h[i]);
		for(auto[l,id]: query[i]){
			ans[id] = -1;
			ans[id] = max(ans[id],get(1,1,n,l,i).mxval);
		}
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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