oj.uz

Submission #123398

# Submission time Handle Problem Language Result Execution time Memory
123398 2019-07-01T11:01:33 Z youngyojun Two Antennas (JOI19_antennas) C++11
22 / 100
 586 ms 32624 KB 
#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;
		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) {
			if(dmx[i] < r) {
				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) return dp[i];
		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]), 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 31672 KB Output is correct
2 Correct 586 ms 32420 KB Output is correct
3 Correct 381 ms 29140 KB Output is correct
4 Correct 555 ms 32320 KB Output is correct
5 Correct 241 ms 26732 KB Output is correct
6 Correct 581 ms 32524 KB Output is correct
7 Correct 489 ms 30728 KB Output is correct
8 Correct 564 ms 32600 KB Output is correct
9 Correct 86 ms 23536 KB Output is correct
10 Correct 571 ms 32624 KB Output is correct
11 Correct 328 ms 28276 KB Output is correct
12 Correct 577 ms 32612 KB Output is correct
13 Correct 385 ms 29780 KB Output is correct
14 Correct 368 ms 29380 KB Output is correct
15 Correct 374 ms 28468 KB Output is correct
16 Correct 356 ms 28720 KB Output is correct
17 Correct 389 ms 30148 KB Output is correct
18 Correct 377 ms 29008 KB Output is correct
19 Correct 386 ms 28856 KB Output is correct
20 Correct 381 ms 29120 KB Output is correct
21 Correct 356 ms 30924 KB Output is correct
22 Correct 372 ms 29328 KB Output is correct
23 Correct 377 ms 29220 KB Output is correct
24 Correct 356 ms 28248 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -