제출 #231615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231615		oolimry	Two Antennas (JOI19_antennas)	C++14	22 / 100	319 ms	26540 KiB

antennas

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

int n, Q;

///SEGMENT TREE BEGIN
static int lazy[400005]; ///smallest height of the right antenna

static int tree[400005]; ///Max Hi if active, else -INF.
static int histMax[400005]; ///histMax = max(tree[i] - lazy[i]);

inline void reset(){
	fill(tree,tree+2*n,-inf);
	fill(lazy,lazy+2*n,inf);
	fill(histMax,histMax+2*n,-inf);
}

inline void relax(int i){
	if(i < n) histMax[i] = max(histMax[i<<1], histMax[i<<1|1]);
	histMax[i] = max(tree[i] - lazy[i], histMax[i]);
}

void prop(int i){
	if(i != 1) prop(i >> 1);
	lazy[i<<1] = min(lazy[i<<1], lazy[i]);
	relax(i<<1);
	lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
	relax(i<<1|1);
	lazy[i] = inf;
}

inline void ptupdate(int i, int v){
	//cout << "Pt: " << i << " " << v << "\n";
	i += n; 
	prop(i >> 1); lazy[i] = inf;
	tree[i] = v; relax(i);
	for(i >>= 1;i > 0;i >>= 1) tree[i] = max(tree[i<<1], tree[i<<1|1]), relax(i);
}

inline void update(int L, int R, int v){
	//cout << "Lazy: " << L << " " << R-1 << " " << v << "\n";
	for(int l = L + n, r = R + n;l < r;l >>= 1,r >>= 1){
		if(l&1){
			lazy[l] = min(lazy[l], v);
			relax(l);
			l++;
		}
		if(r&1){
			r--;
			lazy[r] = min(lazy[r], v);
			relax(r);
		}
	}
	
	for(L += n;L > 0;L >>= 1) relax(L);
	for(R += n-1;R > 0;R >>= 1) relax(R);
}

inline int query(int l, int r){	
	int ans = -inf;
	prop((l+n) >> 1);
	prop((r-1+n) >> 1);
	
	for(l += n,r += n;l < r;l >>= 1,r >>= 1){
		if(l&1){
			//if(l == 5 && r == 8) cout << histMax[l] << "FUNNYTHING\n";
			ans = max(ans,histMax[l]);
			l++;
		}
		if(r&1){
			r--;
			ans = max(ans,histMax[r]);
		}
	}
	return ans;
}
///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 < Q;i++) queries[i].clear();
	reset();
	
	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";
		for(ii e : events[r]){
			if(e.second == 1) ptupdate(e.first, H[e.first]);
			else ptupdate(e.first, -inf);
		}
		
		if(r - A[r] >= 0){
			int R = r - A[r];
			int L = max(0, r - B[r]);
			update(L, R+1, H[r]);
		}
		
		for(ii q : queries[r]){
			int res = query(q.first, r+1);
			//cout << 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: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65