oj.uz

Submission #123395

# Submission time Handle Problem Language Result Execution time Memory
123395 2019-07-01T10:58:49 Z youngyojun Two Antennas (JOI19_antennas) C++11
22 / 100
 582 ms 36716 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() {
		memset(dp, -INF, MAXN*12);
		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 506 ms 35480 KB Output is correct
2 Correct 582 ms 36628 KB Output is correct
3 Correct 440 ms 32100 KB Output is correct
4 Correct 553 ms 36584 KB Output is correct
5 Correct 232 ms 28524 KB Output is correct
6 Correct 545 ms 36632 KB Output is correct
7 Correct 464 ms 34212 KB Output is correct
8 Correct 560 ms 36716 KB Output is correct
9 Correct 85 ms 23800 KB Output is correct
10 Correct 563 ms 36692 KB Output is correct
11 Correct 321 ms 30568 KB Output is correct
12 Correct 550 ms 36716 KB Output is correct
13 Correct 382 ms 33584 KB Output is correct
14 Correct 383 ms 33216 KB Output is correct
15 Correct 375 ms 32332 KB Output is correct
16 Correct 356 ms 32616 KB Output is correct
17 Correct 390 ms 34172 KB Output is correct
18 Correct 378 ms 32968 KB Output is correct
19 Correct 390 ms 32860 KB Output is correct
20 Correct 380 ms 33064 KB Output is correct
21 Correct 352 ms 34728 KB Output is correct
22 Correct 370 ms 33264 KB Output is correct
23 Correct 378 ms 33100 KB Output is correct
24 Correct 354 ms 32108 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 -