Submission #123405

#	Time	Username	Problem	Language	Result	Execution time	Memory
123405		youngyojun	Two Antennas (JOI19_antennas)	C++11	100 / 100	1185 ms	48100 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;
 
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);
	}
	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]), 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: 22 / 22
• Subtask 4: 65 / 65