Submission #503004

#	Time	Username	Problem	Language	Result	Execution time	Memory
503004		sidon	Two Antennas (JOI19_antennas)	C++17	0 / 100	415 ms	62332 KiB

antennas

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

#define remax(X, Y) X = max(X, Y)
#define remin(X, Y) X = min(X, Y)

const int Z = 2e5, INF = 1e12;

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

int N, Q, H[Z], A[Z], B[Z], qL[Z], qR[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; i < Q; ++i) {
		cin >> qL[i] >> qR[i];
		--qL[i], --qR[i];
		qAt[qR[i]].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]) {
				if(j < 0) st.pointUpdate(-j-1, INF);
				else st.pointUpdate(j, H[j]);
			}
			if(i - A[i] >= 0) 
				st.rangeMaximise(max(0LL, i-B[i]), i-A[i]+1, H[i]);
			
			for(int &j : qAt[i])
				ans[j] = max(ans[j], st.rangeMaxDiff(qL[j], i+1));
		}
		if(_) for(int &i : H) i = -i;
	}

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

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