oj.uz

Submission #510277

# Submission time Handle Problem Language Result Execution time Memory
510277 2022-01-14T21:53:06 Z couplefire Two Antennas (JOI19_antennas) C++17
100 / 100
 757 ms 66076 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
#define MAXN 200005
 
const int INF = 1 << 30;
int N, Q;
int H[MAXN], A[MAXN], B[MAXN], L[MAXN], R[MAXN];
int ans[MAXN];
int minc[4*MAXN], maxd[4*MAXN], lazy[4*MAXN];
vector<int> query[MAXN], on[2*MAXN], off[2*MAXN];
 
void spreadlazy(int idx) {
	lazy[idx * 2] = max(lazy[idx * 2], lazy[idx]);
	lazy[idx * 2 + 1] = max(lazy[idx * 2 + 1], lazy[idx]);
	maxd[idx * 2] = max(maxd[idx * 2], lazy[idx * 2] - minc[idx * 2]);
	maxd[idx * 2 + 1] = max(maxd[idx * 2 + 1], lazy[idx * 2 + 1] - minc[idx * 2 + 1]);
	lazy[idx] = -1;
}
 
void updc(int idx, int l, int r, int x, int c) {
	if(l == r) {
		minc[idx] = c;
		lazy[idx] = -1;
		return;
	}
	spreadlazy(idx);
	int m = (l + r) / 2;
	if(x <= m) updc(idx * 2, l, m, x, c);
	else updc(idx * 2 + 1, m + 1, r, x, c);
	minc[idx] = min(minc[idx * 2], minc[idx * 2 + 1]);
	maxd[idx] = max(maxd[idx * 2], maxd[idx * 2 + 1]);
}
 
void updlazy(int idx, int l, int r, int x, int y, int z) {
	if(x <= l && r <= y) {
		lazy[idx] = max(lazy[idx], z);
		maxd[idx] = max(maxd[idx], lazy[idx] - minc[idx]);
		return;
	}
	if(r < x || y < l) return;
	spreadlazy(idx);
	int m = (l + r) / 2;
	updlazy(idx * 2, l, m, x, y, z);
	updlazy(idx * 2 + 1, m + 1, r, x, y, z);
	maxd[idx] = max(maxd[idx * 2], maxd[idx * 2 + 1]);
}
 
int gmaxd(int idx, int l, int r, int x, int y) {
	if(x <= l && r <= y) return maxd[idx];
	if(r < x || y < l) return -1;
	int m = (l + r) / 2;
	spreadlazy(idx);
	return max(gmaxd(idx * 2, l, m, x, y), gmaxd(idx * 2 + 1, m + 1, r, x, y));
}
 
void solve() {
	for(int i = 0; i < N; i++) {
		query[i].clear();
		on[i].clear();
		off[i].clear();
	}
	
	for(int i = 0; i < Q; i++) query[R[i]].push_back(i);
	for(int i = 0; i < N; i++) {
		on[i + A[i]].push_back(i);
		off[i + B[i]].push_back(i);
	}
	for(int i = 1; i < 4 * N; i++) {
		minc[i] = INF;
		maxd[i] = lazy[i] = -1;
	}
 
	for(int i = 0; i < N; i++) {
		for(auto a : on[i]) updc(1, 0, N-1, a, H[a]);
		updlazy(1, 0, N-1, i - B[i], i - A[i], H[i]);
		for(auto a : query[i]) ans[a] = max(ans[a], gmaxd(1, 0, N-1, L[a], i));
		for(auto a : off[i]) updc(1, 0, N-1, a, INF);
	}
}
 
int main() {
	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
	scanf("%d", &Q);
	for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);
 
	for(int i = 0; i < Q; i++) {
		ans[i] = -1;
		L[i]--;
		R[i]--;
	}
	solve();
	for(int i = 0; i < N/2; i++){
		swap(H[i], H[N - i - 1]);
		swap(A[i], A[N - i - 1]);
		swap(B[i], B[N - i - 1]);
	}
	for(int i = 0; i < Q; i++) {
		swap(L[i], R[i]);
		L[i] = N - L[i] - 1;
		R[i] = N - R[i] - 1;
	}
	solve();
 
	for(int i = 0; i < Q; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
antennas.cpp:87:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
antennas.cpp:89:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23760 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 11 ms 23752 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 13 ms 23852 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23988 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23756 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 11 ms 23756 KB Output is correct
17 Correct 11 ms 23800 KB Output is correct
18 Correct 12 ms 23768 KB Output is correct
19 Correct 12 ms 23756 KB Output is correct
20 Correct 12 ms 23772 KB Output is correct
21 Correct 11 ms 23756 KB Output is correct
22 Correct 12 ms 23820 KB Output is correct
23 Correct 12 ms 23764 KB Output is correct
24 Correct 12 ms 23756 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23760 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 11 ms 23752 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 13 ms 23852 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23988 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23756 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 11 ms 23756 KB Output is correct
17 Correct 11 ms 23800 KB Output is correct
18 Correct 12 ms 23768 KB Output is correct
19 Correct 12 ms 23756 KB Output is correct
20 Correct 12 ms 23772 KB Output is correct
21 Correct 11 ms 23756 KB Output is correct
22 Correct 12 ms 23820 KB Output is correct
23 Correct 12 ms 23764 KB Output is correct
24 Correct 12 ms 23756 KB Output is correct
25 Correct 121 ms 29240 KB Output is correct
26 Correct 27 ms 24672 KB Output is correct
27 Correct 171 ms 31456 KB Output is correct
28 Correct 154 ms 31584 KB Output is correct
29 Correct 114 ms 29368 KB Output is correct
30 Correct 111 ms 29160 KB Output is correct
31 Correct 118 ms 30688 KB Output is correct
32 Correct 153 ms 31520 KB Output is correct
33 Correct 176 ms 31056 KB Output is correct
34 Correct 84 ms 27588 KB Output is correct
35 Correct 184 ms 31552 KB Output is correct
36 Correct 172 ms 31480 KB Output is correct
37 Correct 99 ms 27784 KB Output is correct
38 Correct 184 ms 30556 KB Output is correct
39 Correct 35 ms 24860 KB Output is correct
40 Correct 190 ms 30540 KB Output is correct
41 Correct 124 ms 28944 KB Output is correct
42 Correct 168 ms 30508 KB Output is correct
43 Correct 84 ms 26148 KB Output is correct
44 Correct 157 ms 30472 KB Output is correct
45 Correct 40 ms 25180 KB Output is correct
46 Correct 164 ms 30524 KB Output is correct
47 Correct 51 ms 25660 KB Output is correct
48 Correct 160 ms 30652 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 50756 KB Output is correct
2 Correct 413 ms 53920 KB Output is correct
3 Correct 259 ms 45000 KB Output is correct
4 Correct 392 ms 53964 KB Output is correct
5 Correct 171 ms 37556 KB Output is correct
6 Correct 394 ms 53912 KB Output is correct
7 Correct 342 ms 49876 KB Output is correct
8 Correct 392 ms 53900 KB Output is correct
9 Correct 53 ms 28528 KB Output is correct
10 Correct 424 ms 53912 KB Output is correct
11 Correct 250 ms 42592 KB Output is correct
12 Correct 415 ms 53908 KB Output is correct
13 Correct 249 ms 49184 KB Output is correct
14 Correct 252 ms 48728 KB Output is correct
15 Correct 238 ms 48480 KB Output is correct
16 Correct 237 ms 49156 KB Output is correct
17 Correct 272 ms 49520 KB Output is correct
18 Correct 246 ms 48416 KB Output is correct
19 Correct 245 ms 48520 KB Output is correct
20 Correct 242 ms 48800 KB Output is correct
21 Correct 244 ms 49736 KB Output is correct
22 Correct 242 ms 48980 KB Output is correct
23 Correct 244 ms 48844 KB Output is correct
24 Correct 229 ms 48404 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23760 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 11 ms 23752 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 13 ms 23852 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23988 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23756 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23884 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 11 ms 23756 KB Output is correct
17 Correct 11 ms 23800 KB Output is correct
18 Correct 12 ms 23768 KB Output is correct
19 Correct 12 ms 23756 KB Output is correct
20 Correct 12 ms 23772 KB Output is correct
21 Correct 11 ms 23756 KB Output is correct
22 Correct 12 ms 23820 KB Output is correct
23 Correct 12 ms 23764 KB Output is correct
24 Correct 12 ms 23756 KB Output is correct
25 Correct 121 ms 29240 KB Output is correct
26 Correct 27 ms 24672 KB Output is correct
27 Correct 171 ms 31456 KB Output is correct
28 Correct 154 ms 31584 KB Output is correct
29 Correct 114 ms 29368 KB Output is correct
30 Correct 111 ms 29160 KB Output is correct
31 Correct 118 ms 30688 KB Output is correct
32 Correct 153 ms 31520 KB Output is correct
33 Correct 176 ms 31056 KB Output is correct
34 Correct 84 ms 27588 KB Output is correct
35 Correct 184 ms 31552 KB Output is correct
36 Correct 172 ms 31480 KB Output is correct
37 Correct 99 ms 27784 KB Output is correct
38 Correct 184 ms 30556 KB Output is correct
39 Correct 35 ms 24860 KB Output is correct
40 Correct 190 ms 30540 KB Output is correct
41 Correct 124 ms 28944 KB Output is correct
42 Correct 168 ms 30508 KB Output is correct
43 Correct 84 ms 26148 KB Output is correct
44 Correct 157 ms 30472 KB Output is correct
45 Correct 40 ms 25180 KB Output is correct
46 Correct 164 ms 30524 KB Output is correct
47 Correct 51 ms 25660 KB Output is correct
48 Correct 160 ms 30652 KB Output is correct
49 Correct 348 ms 50756 KB Output is correct
50 Correct 413 ms 53920 KB Output is correct
51 Correct 259 ms 45000 KB Output is correct
52 Correct 392 ms 53964 KB Output is correct
53 Correct 171 ms 37556 KB Output is correct
54 Correct 394 ms 53912 KB Output is correct
55 Correct 342 ms 49876 KB Output is correct
56 Correct 392 ms 53900 KB Output is correct
57 Correct 53 ms 28528 KB Output is correct
58 Correct 424 ms 53912 KB Output is correct
59 Correct 250 ms 42592 KB Output is correct
60 Correct 415 ms 53908 KB Output is correct
61 Correct 249 ms 49184 KB Output is correct
62 Correct 252 ms 48728 KB Output is correct
63 Correct 238 ms 48480 KB Output is correct
64 Correct 237 ms 49156 KB Output is correct
65 Correct 272 ms 49520 KB Output is correct
66 Correct 246 ms 48416 KB Output is correct
67 Correct 245 ms 48520 KB Output is correct
68 Correct 242 ms 48800 KB Output is correct
69 Correct 244 ms 49736 KB Output is correct
70 Correct 242 ms 48980 KB Output is correct
71 Correct 244 ms 48844 KB Output is correct
72 Correct 229 ms 48404 KB Output is correct
73 Correct 574 ms 60340 KB Output is correct
74 Correct 409 ms 55268 KB Output is correct
75 Correct 551 ms 55780 KB Output is correct
76 Correct 699 ms 66000 KB Output is correct
77 Correct 352 ms 45380 KB Output is correct
78 Correct 610 ms 62856 KB Output is correct
79 Correct 630 ms 61596 KB Output is correct
80 Correct 757 ms 65988 KB Output is correct
81 Correct 253 ms 36816 KB Output is correct
82 Correct 531 ms 60912 KB Output is correct
83 Correct 485 ms 53312 KB Output is correct
84 Correct 703 ms 66076 KB Output is correct
85 Correct 425 ms 56448 KB Output is correct
86 Correct 524 ms 59504 KB Output is correct
87 Correct 280 ms 50624 KB Output is correct
88 Correct 518 ms 60216 KB Output is correct
89 Correct 473 ms 58236 KB Output is correct
90 Correct 557 ms 59404 KB Output is correct
91 Correct 347 ms 53308 KB Output is correct
92 Correct 537 ms 59856 KB Output is correct
93 Correct 291 ms 52372 KB Output is correct
94 Correct 555 ms 59964 KB Output is correct
95 Correct 320 ms 52608 KB Output is correct
96 Correct 527 ms 59372 KB Output is correct