Submission #231708

#	Time	Username	Problem	Language	Result	Execution time	Memory
231708		oolimry	Two Antennas (JOI19_antennas)	C++14	100 / 100	850 ms	71708 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf = 1e9 + 100;

int n, Q;

///SEGMENT TREE BEGIN
struct node{
	int s, e, m, C, lazy, D;
	node *l, *r;
	
	node(int _s, int _e){
		s = _s; e = _e;
		m = (s+e)/2;
		C = -inf, lazy = inf, D = -inf;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void push(){
		if(lazy != inf){
			l->lazy = min(l->lazy, lazy);
			r->lazy = min(r->lazy, lazy);
			
			l->D = max(l->D, l->C - lazy);
			r->D = max(r->D, r->C - lazy);
			
			lazy = inf;
		}
	}
	
	void pull(){
		C = max(l->C, r->C);
		D = max(l->D, r->D);
	}
	
	void updateC(int i, int H){
		if(s == e){
			C = H;
			return;
		}
		push();
		if(i <= m) l->updateC(i, H);
		else r->updateC(i, H);
		pull();
	}
	
	void updateLazy(int L, int R, int H){
		if(s == L && e == R){
			D = max(D, C - H);
			lazy = min(lazy, H);
			return;
		}
		push();
		
		if(R <= m) l->updateLazy(L, R, H);
		else if(L >= m+1) r->updateLazy(L, R, H);
		else{
			l->updateLazy(L, m, H);
			r->updateLazy(m+1, R, H);
		}
		pull();
	}
	
	int query(int L, int R){
		
		//if(s == 0 && e == n-1) cout << "Q: " << L << " " << R <<"\n";
		
		if(s == L && e == R) return D;
		
		push();
		
		if(R <= m) return l->query(L, R);
		else if(L >= m+1) return r->query(L, R);
		else{
			return max(l->query(L, m), r->query(m+1, R));
		}
	}
} *root;
///SEGMENT TREE END

int H[200005];
int A[200005];
int B[200005];
int ans[200005];
ii QQ[200005];
vector<ii> queries[200005];
vector<ii> events[200005];

void solve(){
	for(int i = 0;i < n;i++) events[i].clear();
	for(int i = 0;i < n;i++) queries[i].clear();
	
	root = new node(0, n-1);
	
	for(int i = 0;i < n;i++){
		int start = i + A[i], end = i + B[i] + 1;
		if(start < n) events[start].push_back(ii(i, 1)); ///1 is start
		if(end < n) events[end].push_back(ii(i, -1)); ///-1 is end
	}
	
	for(int i = 0;i < Q;i++){
		queries[QQ[i].second].push_back(ii(QQ[i].first, i));
	}
	
	for(int r = 0;r < n;r++){
		//cout << r << ":\n";
		
		sort(events[r].begin(),events[r].end());
		
		for(ii e : events[r]){
			if(e.second == 1) root->updateC(e.first, H[e.first]);
			else root->updateC(e.first, -inf);
		}
		
		if(r - A[r] >= 0){
			int R = r - A[r];
			int L = max(0, r - B[r]);
			root->updateLazy(L, R, H[r]);
		}
		
		for(ii q : queries[r]){
			int res = root->query(q.first, r);
			//cout << q.second << " " << q.first << " " << r << " " << res << "\n";
			ans[q.second] = max(ans[q.second],res);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0;i < n;i++) cin >> H[i] >> A[i] >> B[i];
	
	cin >> Q;
	fill(ans,ans+Q, -inf);
	
	for(int i = 0;i < Q;i++){
		int l, r; cin >> l >> r; l--; r--;
		QQ[i] = ii(l,r);
	}
	
	solve();
	
	reverse(H,H+n);
	reverse(A,A+n);
	reverse(B,B+n);
	for(int i = 0;i < Q;i++){
		QQ[i].first = n - 1 - QQ[i].first;
		QQ[i].second = n - 1 - QQ[i].second;
		swap(QQ[i].first,QQ[i].second);
	}
	
	solve();
	
	for(int i = 0;i < Q;i++) cout << max(-1,ans[i]) << "\n";
}

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