Submission #123404

#	Time	Username	Problem	Language	Result	Execution time	Memory
123404		youngyojun	Two Antennas (JOI19_antennas)	C++11	13 / 100	3048 ms	29392 KiB

antennas

#include <bits/stdc++.h>
#define eb emplace_back
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;

const int MAXN = 200055;
const int MAXQ = 200055;

struct SEG {
	SEG() { init(); }
	int dp[MAXN*3], dmn[MAXN*3], dmx[MAXN*3];

	void init() {
		fill(dp, dp+MAXN*3, -INF);
		fill(dmn, dmn+MAXN*3, INF);
		memset(dmx, 0, MAXN*12);
	}

	void prop(int i, int s, int e) {
		upmax(dp[i], dmx[i] - dmn[i]);
		if(s != e) {
			upmax(dmx[i<<1], dmx[i]);
			upmax(dmx[i<<1|1], dmx[i]);
		}
		dmx[i] = 0;
	}
	void cal(int i, int s, int e) {
		if(s == e) return;
		upmax(dp[i], max(dp[i<<1], dp[i<<1|1]));
		dmn[i] = min(dmn[i<<1], dmn[i<<1|1]);
	}
	void upd(int i, int s, int e, int p, int q, int r) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dmx[i] = r;
			upmax(dp[i], r - dmn[i]);
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|1, m+1, e, p, q, r);
		cal(i, s, e);
	}
	void upd(int i, int s, int e, int x, int r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			dmn[i] = r;
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, x, r);
		upd(i<<1|1, m+1, e, x, r);
		cal(i, s, e);
	}
	int get(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return -INF;
		if(p <= s && e <= q) {
			int ret = dp[i];
			cal(i, s, e);
			return ret;
		}
		int m = (s+e) >> 1;
		int ret = max(get(i<<1, s, m, p, q), get(i<<1|1, m+1, e, p, q));
		cal(i, s, e);
		return ret;
	}
} seg;

vector<int> PushV[MAXN], PopV[MAXN], QV[MAXN];

int A[MAXN], B[MAXN], H[MAXN];
int S[MAXQ], E[MAXQ];

int Ans[MAXQ];
int N, Q;

int dp[MAXN], dc[MAXN];
void solve() {
	for(int i = 1; i <= Q; i++) QV[E[i]].eb(i);
	for(int i = 1; i <= N; i++) {
		PushV[min(N+1, i+A[i])].eb(i);
		PopV[min(N+1, i+B[i]+1)].eb(i);
	}
	fill(dp, dp+N+1, -INF);
	fill(dc, dc+N+1, INF);
	for(int j = 1; j <= N; j++) {
		for(int i : PushV[j]) dc[i] = H[i];
		for(int i : PopV[j]) dc[i] = INF;
		for(int i = max(1, j-B[j]); i <= j-A[j]; i++)
			upmax(dp[i], H[j] - dc[i]);
		for(int q : QV[j]) {
			int ret = -INF;
			for(int i = S[q]; i < E[q]; i++)
				upmax(ret, dp[i]);
			upmax(Ans[q], ret);
		}
	}
	/*
	for(int j = 1; j <= N; j++) {
		for(int i : PushV[j]) seg.upd(1, 1, N, i, H[i]);
		for(int i : PopV[j]) seg.upd(1, 1, N, i, INF);
		seg.upd(1, 1, N, max(1, j-B[j]), max(1, j-A[j]), H[j]);
		for(int q : QV[j]) upmax(Ans[q], seg.get(1, 1, N, S[q], j-1));
	}
	*/
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N; for(int i = 1; i <= N; i++) cin >> H[i] >> A[i] >> B[i];
	cin >> Q; for(int i = 1; i <= Q; i++) cin >> S[i] >> E[i];

	fill(Ans, Ans+Q+1, -1);
	solve();

	seg.init();
	reverse(A+1, A+N+1);
	reverse(B+1, B+N+1);
	reverse(H+1, H+N+1);
	for(int i = 1; i <= Q; i++) {
		swap(S[i], E[i]);
		S[i] = N-S[i]+1;
		E[i] = N-E[i]+1;
	}
	for(int i = 0; i <= N; i++) {
		PushV[i].clear();
		PopV[i].clear();
		QV[i].clear();
	}

	solve();

	for(int i = 1; i <= Q; i++) printf("%d\n", Ans[i]);
	return 0;
}

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