oj.uz

Submission #503009

# Submission time Handle Problem Language Result Execution time Memory
503009 2022-01-06T22:00:03 Z sidon Two Antennas (JOI19_antennas) C++17
100 / 100
 710 ms 59584 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 2e5, INF = 1e9+1;

int sL, sR, sV;
struct SegmentTree{
	int l, r, x = INF, y = -INF, res = -INF;
	SegmentTree *L, *R;
	void pull() {
		x = min(L->x, R->x);
		res = max({L->res, R->res, y - x});
	}
	void apply(int val) {
		y = max(y, val);
		res = max(res, y - x);
	}
	void push() {
		L->apply(y), R->apply(y);
		y = -INF;
	}
	SegmentTree(int lx, int rx) : l(lx), r(rx) {
		if(r - l < 2) return;
		int m = (l + r) / 2;
		L = new SegmentTree(l, m);
		R = new SegmentTree(m, r);
	}
	void update0() {
		if(sL<=l && r<=sR) return apply(sV);
		if(sR<=l || r<=sL) return;
		push();
		L->update0(), R->update0();
		pull();
	}
	void update1() {
		if(r - l < 2)
			y = -INF, x = sV, res = max(res, y - x);
		else
			push(), (sL < L->r ? L : R)->update1(), pull();
	}
	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], 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, qR; i < Q; ++i) {
		cin >> qL[i] >> qR;
		--qL[i];
		qAt[--qR].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])
				sL = max(j, -j-1), sV = j < 0 ? INF : H[j], st.update1();
			if(i - A[i] >= 0) 
				sL = max(0, i-B[i]), sR = i-A[i]+1, sV = H[i], st.update0();
			for(int &j : qAt[i])
				sL = qL[j], sR = N, ans[j] = max(ans[j], st.query());
		}
		if(_) for(int &i : H) i = -i;
	}
	for(int i = 0; i < Q; ++i)
		cout << ans[i] << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10572 KB Output is correct
3 Correct 5 ms 10572 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 5 ms 10572 KB Output is correct
8 Correct 6 ms 10500 KB Output is correct
9 Correct 5 ms 10444 KB Output is correct
10 Correct 7 ms 10572 KB Output is correct
11 Correct 5 ms 10444 KB Output is correct
12 Correct 6 ms 10572 KB Output is correct
13 Correct 6 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 6 ms 10444 KB Output is correct
16 Correct 7 ms 10572 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10572 KB Output is correct
19 Correct 5 ms 10444 KB Output is correct
20 Correct 7 ms 10532 KB Output is correct
21 Correct 6 ms 10444 KB Output is correct
22 Correct 6 ms 10500 KB Output is correct
23 Correct 5 ms 10444 KB Output is correct
24 Correct 7 ms 10552 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10572 KB Output is correct
3 Correct 5 ms 10572 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 5 ms 10572 KB Output is correct
8 Correct 6 ms 10500 KB Output is correct
9 Correct 5 ms 10444 KB Output is correct
10 Correct 7 ms 10572 KB Output is correct
11 Correct 5 ms 10444 KB Output is correct
12 Correct 6 ms 10572 KB Output is correct
13 Correct 6 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 6 ms 10444 KB Output is correct
16 Correct 7 ms 10572 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10572 KB Output is correct
19 Correct 5 ms 10444 KB Output is correct
20 Correct 7 ms 10532 KB Output is correct
21 Correct 6 ms 10444 KB Output is correct
22 Correct 6 ms 10500 KB Output is correct
23 Correct 5 ms 10444 KB Output is correct
24 Correct 7 ms 10552 KB Output is correct
25 Correct 71 ms 14144 KB Output is correct
26 Correct 14 ms 11300 KB Output is correct
27 Correct 95 ms 15300 KB Output is correct
28 Correct 100 ms 15416 KB Output is correct
29 Correct 66 ms 13872 KB Output is correct
30 Correct 68 ms 13948 KB Output is correct
31 Correct 76 ms 14708 KB Output is correct
32 Correct 99 ms 15376 KB Output is correct
33 Correct 90 ms 14940 KB Output is correct
34 Correct 50 ms 13052 KB Output is correct
35 Correct 99 ms 15168 KB Output is correct
36 Correct 98 ms 15300 KB Output is correct
37 Correct 58 ms 12868 KB Output is correct
38 Correct 95 ms 14324 KB Output is correct
39 Correct 19 ms 11340 KB Output is correct
40 Correct 95 ms 14336 KB Output is correct
41 Correct 73 ms 13400 KB Output is correct
42 Correct 98 ms 14356 KB Output is correct
43 Correct 36 ms 12028 KB Output is correct
44 Correct 101 ms 14340 KB Output is correct
45 Correct 22 ms 11468 KB Output is correct
46 Correct 98 ms 14368 KB Output is correct
47 Correct 29 ms 11724 KB Output is correct
48 Correct 94 ms 14336 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 48648 KB Output is correct
2 Correct 392 ms 52704 KB Output is correct
3 Correct 253 ms 40128 KB Output is correct
4 Correct 390 ms 52744 KB Output is correct
5 Correct 151 ms 29988 KB Output is correct
6 Correct 433 ms 52644 KB Output is correct
7 Correct 334 ms 47140 KB Output is correct
8 Correct 392 ms 52696 KB Output is correct
9 Correct 44 ms 17160 KB Output is correct
10 Correct 390 ms 52644 KB Output is correct
11 Correct 220 ms 36932 KB Output is correct
12 Correct 384 ms 52688 KB Output is correct
13 Correct 254 ms 50628 KB Output is correct
14 Correct 234 ms 50740 KB Output is correct
15 Correct 225 ms 50836 KB Output is correct
16 Correct 208 ms 51164 KB Output is correct
17 Correct 249 ms 50920 KB Output is correct
18 Correct 225 ms 51276 KB Output is correct
19 Correct 250 ms 50568 KB Output is correct
20 Correct 225 ms 50688 KB Output is correct
21 Correct 217 ms 50644 KB Output is correct
22 Correct 233 ms 50832 KB Output is correct
23 Correct 232 ms 50600 KB Output is correct
24 Correct 206 ms 50740 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10572 KB Output is correct
3 Correct 5 ms 10572 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 5 ms 10572 KB Output is correct
8 Correct 6 ms 10500 KB Output is correct
9 Correct 5 ms 10444 KB Output is correct
10 Correct 7 ms 10572 KB Output is correct
11 Correct 5 ms 10444 KB Output is correct
12 Correct 6 ms 10572 KB Output is correct
13 Correct 6 ms 10444 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 6 ms 10444 KB Output is correct
16 Correct 7 ms 10572 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10572 KB Output is correct
19 Correct 5 ms 10444 KB Output is correct
20 Correct 7 ms 10532 KB Output is correct
21 Correct 6 ms 10444 KB Output is correct
22 Correct 6 ms 10500 KB Output is correct
23 Correct 5 ms 10444 KB Output is correct
24 Correct 7 ms 10552 KB Output is correct
25 Correct 71 ms 14144 KB Output is correct
26 Correct 14 ms 11300 KB Output is correct
27 Correct 95 ms 15300 KB Output is correct
28 Correct 100 ms 15416 KB Output is correct
29 Correct 66 ms 13872 KB Output is correct
30 Correct 68 ms 13948 KB Output is correct
31 Correct 76 ms 14708 KB Output is correct
32 Correct 99 ms 15376 KB Output is correct
33 Correct 90 ms 14940 KB Output is correct
34 Correct 50 ms 13052 KB Output is correct
35 Correct 99 ms 15168 KB Output is correct
36 Correct 98 ms 15300 KB Output is correct
37 Correct 58 ms 12868 KB Output is correct
38 Correct 95 ms 14324 KB Output is correct
39 Correct 19 ms 11340 KB Output is correct
40 Correct 95 ms 14336 KB Output is correct
41 Correct 73 ms 13400 KB Output is correct
42 Correct 98 ms 14356 KB Output is correct
43 Correct 36 ms 12028 KB Output is correct
44 Correct 101 ms 14340 KB Output is correct
45 Correct 22 ms 11468 KB Output is correct
46 Correct 98 ms 14368 KB Output is correct
47 Correct 29 ms 11724 KB Output is correct
48 Correct 94 ms 14336 KB Output is correct
49 Correct 355 ms 48648 KB Output is correct
50 Correct 392 ms 52704 KB Output is correct
51 Correct 253 ms 40128 KB Output is correct
52 Correct 390 ms 52744 KB Output is correct
53 Correct 151 ms 29988 KB Output is correct
54 Correct 433 ms 52644 KB Output is correct
55 Correct 334 ms 47140 KB Output is correct
56 Correct 392 ms 52696 KB Output is correct
57 Correct 44 ms 17160 KB Output is correct
58 Correct 390 ms 52644 KB Output is correct
59 Correct 220 ms 36932 KB Output is correct
60 Correct 384 ms 52688 KB Output is correct
61 Correct 254 ms 50628 KB Output is correct
62 Correct 234 ms 50740 KB Output is correct
63 Correct 225 ms 50836 KB Output is correct
64 Correct 208 ms 51164 KB Output is correct
65 Correct 249 ms 50920 KB Output is correct
66 Correct 225 ms 51276 KB Output is correct
67 Correct 250 ms 50568 KB Output is correct
68 Correct 225 ms 50688 KB Output is correct
69 Correct 217 ms 50644 KB Output is correct
70 Correct 233 ms 50832 KB Output is correct
71 Correct 232 ms 50600 KB Output is correct
72 Correct 206 ms 50740 KB Output is correct
73 Correct 574 ms 53692 KB Output is correct
74 Correct 413 ms 53308 KB Output is correct
75 Correct 538 ms 46372 KB Output is correct
76 Correct 710 ms 59492 KB Output is correct
77 Correct 306 ms 34500 KB Output is correct
78 Correct 597 ms 57596 KB Output is correct
79 Correct 628 ms 53780 KB Output is correct
80 Correct 707 ms 59584 KB Output is correct
81 Correct 194 ms 22208 KB Output is correct
82 Correct 560 ms 56460 KB Output is correct
83 Correct 496 ms 43088 KB Output is correct
84 Correct 706 ms 59492 KB Output is correct
85 Correct 424 ms 54432 KB Output is correct
86 Correct 531 ms 56340 KB Output is correct
87 Correct 273 ms 51828 KB Output is correct
88 Correct 515 ms 56804 KB Output is correct
89 Correct 482 ms 55280 KB Output is correct
90 Correct 534 ms 56920 KB Output is correct
91 Correct 336 ms 52836 KB Output is correct
92 Correct 522 ms 56392 KB Output is correct
93 Correct 286 ms 52024 KB Output is correct
94 Correct 529 ms 56456 KB Output is correct
95 Correct 311 ms 52512 KB Output is correct
96 Correct 496 ms 56352 KB Output is correct