Submission #503008

#	Time	Username	Problem	Language	Result	Execution time	Memory
503008		sidon	Two Antennas (JOI19_antennas)	C++17	100 / 100	775 ms	59584 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

const int Z = 2e5, INF = 1e9+1;

int sL, sR, sV;
struct SegmentTree{
	int l, r, x = INF, y = -INF, res = -INF;
	SegmentTree *L, *R;
	void pull() {
		x = min(L->x, R->x);
		res = max({L->res, R->res, y - x});
	}
	void apply(int val) {
		y = max(y, val);
		res = max(res, y - x);
	}
	void push() {
		L->apply(y), R->apply(y);
		y = -INF;
	}
	SegmentTree(int lx, int rx) : l(lx), r(rx) {
		if(r - l < 2) return;
		int m = (l + r) / 2;
		L = new SegmentTree(l, m);
		R = new SegmentTree(m, r);
	}
	void rangeMaximise() {
		if(sL<=l && r<=sR) return apply(sV);
		if(sR<=l || r<=sL) return;
		push();
		L->rangeMaximise(), R->rangeMaximise();
		pull();
	}
	void pointUpdate() {
		if(r - l < 2)
			y = -INF, x = sV, res = max(res, y - x);
		else
			push(), (sL < L->r ? L : R)->pointUpdate(), pull();
	}
	int rangeMaxDiff() {
		if(sL<=l && r<=sR) return res;
		if(sR<=l || r<=sL) return -INF;
		push();
		return max(L->rangeMaxDiff(), R->rangeMaxDiff());
	}
};

int N, Q, H[Z], A[Z], B[Z], qL[Z], ans[Z];
vector<int> add[Z+1], qAt[Z];

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> N;

	for(int i = 0; i < N; ++i) {
		cin >> H[i] >> A[i] >> B[i];

		if(i + A[i] <  N) {
			add[i + A[i]].push_back(i);
			add[min(N, i+B[i]+1)].push_back(-i-1);
		}
	}
	cin >> Q;
	
	for(int i = 0, qR; i < Q; ++i) {
		cin >> qL[i] >> qR;
		--qL[i];
		qAt[--qR].push_back(i);
		ans[i] = -1;
	}

	for(int _ : {1, 0}) {
		SegmentTree st(0, N);
		for(int i = 0; i < N; ++i) {
			for(int &j : add[i])
				sL = max(j, -j-1), sV = j < 0 ? INF : H[j], st.pointUpdate();
			if(i - A[i] >= 0) 
				sL = max(0, i-B[i]), sR = i-A[i]+1, sV = H[i], st.rangeMaximise();
			for(int &j : qAt[i])
				sL = qL[j], sR = N, ans[j] = max(ans[j], st.rangeMaxDiff());
		}
		if(_) for(int &i : H) i = -i;
	}

	for(int i = 0; i < Q; ++i)
		cout << ans[i] << '\n';
}

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