Submission #1220141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220141		emptypringlescan	Two Antennas (JOI19_antennas)	C++17	0 / 100	266 ms	57644 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int s,e,m;
	node *l,*r;
	long long bigdif;
	pair<long long,long long> pt;
	pair<long long,long long> ran; //lazy
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		bigdif=-1;
		pt={1e16,-1};
		ran={1e16,-1};
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(s!=e&&ran.second!=-1){
			l->bigdif=max({l->bigdif,ran.second-l->pt.first,l->pt.second-ran.first});
			l->ran.first=min(l->ran.first,ran.first);
			l->ran.second=max(l->ran.second,ran.second);
			r->bigdif=max({r->bigdif,ran.second-r->pt.first,r->pt.second-ran.first});
			r->ran.first=min(r->ran.first,ran.first);
			r->ran.second=max(r->ran.second,ran.second);
			ran={1e16,-1};
		}
	}
	void turn(int S, long long V){
		if(s==e){
			if(V>-1) pt={V,V};
			else pt={1e16,-1};
			return;
		}
		prop();
		if(S<=m) l->turn(S,V);
		else r->turn(S,V);
		pt.first=min(l->pt.first,r->pt.first);
		pt.second=max(l->pt.second,r->pt.second);
	}
	void addran(int S, int E, long long V){
		if(S<=s&&e<=E){
			ran.first=min(ran.first,V);
			ran.second=max(ran.second,V);
			bigdif=max({bigdif,pt.second-ran.first,ran.second-pt.first});
			return;
		}
		prop();
		if(E<=m) l->addran(S,E,V);
		else if(S>m) r->addran(S,E,V);
		else l->addran(S,m,V),r->addran(m+1,E,V);
		bigdif=max({bigdif,l->bigdif,r->bigdif});
	}
	long long query(int S, int E){
		if(S<=s&&e<=E) return bigdif;
		prop();
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return max(l->query(S,m),r->query(m+1,E));
	}
} *root;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	long long arr[n+1];
	pair<int,int> can[n+1];
	vector<int> act[n+2],deact[n+2];
	for(int i=1; i<=n; i++){
		long long a;
		int b,c;
		cin >> a >> b >> c;
		arr[i]=a;
		if(i<=b) can[i]={-1,-1};
		else can[i]={max(1ll,i-c),i-b};
		act[min(n+1,i+b)].push_back(i);
		deact[min(n+1,i+c+1)].push_back(i);
	}
	int q;
	cin >> q;
	long long ans[q];
	pair<pair<int,int>,int> qu[q];
	for(int i=0; i<q; i++){
		cin >> qu[i].first.second >> qu[i].first.first;
		qu[i].second=i;
	}
	sort(qu,qu+q);
	root=new node(1,n);
	int cur=0;
	for(int i=1; i<=n; i++){
		for(int j:act[i]) root->turn(j,arr[j]);
		for(int j:deact[i]) root->turn(j,-1);
		if(can[i].first!=-1) root->addran(can[i].first,can[i].second,arr[i]);
		while(cur<q&&qu[cur].first.first==i){
			ans[qu[cur].second]=root->query(qu[cur].first.second,qu[cur].first.first);
			cur++;
		}
	}
	for(int i=0; i<q; i++) cout << max(-1ll,ans[i]) << '\n';
}

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