#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define PI 2*acos(0.0)
void solve(int test) {
int n, q;
cin >> n;
vector <int> h(n), a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> h[i] >> a[i] >> b[i];
}
if (n <= 2000) {
int cost[n][n][20], lg[n + 1], left[n][n], right[n][n];
lg[1] = 0;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
right[i][j] = -1;
left[i][j] = -1;
for (int k = 0; k < 20; k++) {
cost[i][j][k] = -1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (max(a[i], a[j]) <= j - i && j - i <= min(b[i], b[j])) {
right[i][j] = abs(h[i] - h[j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
right[j][i] = max(right[j][i], right[j + 1][i]);
}
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
cost[i][j][0] = right[i][j];
}
}
//~ for (int i = 0; i < n; i++) {
//~ for (int j = i; j < n; j++) {
//~ cout << cost[i][j][0] << ' ';
//~ }
//~ cout << endl;
//~ }
for (int l = 0; l < n; l++) {
for (int j = 1; j < 20; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
cost[l][i][j] = max(cost[l][i][j - 1], cost[l][i + (1 << (j - 1))][j - 1]);
}
}
}
int q;
cin >> q;
vector <pair <pii, int>> queries(q);
for (int i = 0; i < q; i++) {
cin >> queries[i].first.first >> queries[i].first.second;
queries[i].second = i;
int l = queries[i].first.first, r = queries[i].first.second;
l--;r --;
int j = lg[r - l + 1];
//~ cout << l << ' ' << r << ' ' << j << endl;
cout << max(cost[l][l][j], cost[l][r - (1 << j) + 1][j]) << endl;
}
}
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
return 0;
}
Compilation message
antennas.cpp: In function 'void solve(int)':
antennas.cpp:29:40: warning: variable 'left' set but not used [-Wunused-but-set-variable]
29 | int cost[n][n][20], lg[n + 1], left[n][n], right[n][n];
| ^~~~
antennas.cpp:22:12: warning: unused variable 'q' [-Wunused-variable]
22 | int n, q;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1364 KB |
Output is correct |
2 |
Correct |
10 ms |
8076 KB |
Output is correct |
3 |
Correct |
4 ms |
4820 KB |
Output is correct |
4 |
Correct |
7 ms |
8008 KB |
Output is correct |
5 |
Correct |
4 ms |
5824 KB |
Output is correct |
6 |
Correct |
10 ms |
8076 KB |
Output is correct |
7 |
Correct |
8 ms |
6848 KB |
Output is correct |
8 |
Correct |
6 ms |
8000 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
6 ms |
8020 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
9 ms |
8004 KB |
Output is correct |
13 |
Correct |
4 ms |
5588 KB |
Output is correct |
14 |
Correct |
4 ms |
5716 KB |
Output is correct |
15 |
Correct |
4 ms |
5600 KB |
Output is correct |
16 |
Correct |
6 ms |
5708 KB |
Output is correct |
17 |
Correct |
4 ms |
5888 KB |
Output is correct |
18 |
Correct |
6 ms |
5588 KB |
Output is correct |
19 |
Correct |
5 ms |
5716 KB |
Output is correct |
20 |
Correct |
6 ms |
5796 KB |
Output is correct |
21 |
Correct |
6 ms |
5588 KB |
Output is correct |
22 |
Correct |
6 ms |
5844 KB |
Output is correct |
23 |
Correct |
5 ms |
5760 KB |
Output is correct |
24 |
Correct |
6 ms |
5736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1364 KB |
Output is correct |
2 |
Correct |
10 ms |
8076 KB |
Output is correct |
3 |
Correct |
4 ms |
4820 KB |
Output is correct |
4 |
Correct |
7 ms |
8008 KB |
Output is correct |
5 |
Correct |
4 ms |
5824 KB |
Output is correct |
6 |
Correct |
10 ms |
8076 KB |
Output is correct |
7 |
Correct |
8 ms |
6848 KB |
Output is correct |
8 |
Correct |
6 ms |
8000 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
6 ms |
8020 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
9 ms |
8004 KB |
Output is correct |
13 |
Correct |
4 ms |
5588 KB |
Output is correct |
14 |
Correct |
4 ms |
5716 KB |
Output is correct |
15 |
Correct |
4 ms |
5600 KB |
Output is correct |
16 |
Correct |
6 ms |
5708 KB |
Output is correct |
17 |
Correct |
4 ms |
5888 KB |
Output is correct |
18 |
Correct |
6 ms |
5588 KB |
Output is correct |
19 |
Correct |
5 ms |
5716 KB |
Output is correct |
20 |
Correct |
6 ms |
5796 KB |
Output is correct |
21 |
Correct |
6 ms |
5588 KB |
Output is correct |
22 |
Correct |
6 ms |
5844 KB |
Output is correct |
23 |
Correct |
5 ms |
5760 KB |
Output is correct |
24 |
Correct |
6 ms |
5736 KB |
Output is correct |
25 |
Correct |
98 ms |
69192 KB |
Output is correct |
26 |
Correct |
374 ms |
345224 KB |
Output is correct |
27 |
Correct |
333 ms |
238020 KB |
Output is correct |
28 |
Correct |
402 ms |
350720 KB |
Output is correct |
29 |
Correct |
148 ms |
83904 KB |
Output is correct |
30 |
Correct |
389 ms |
348616 KB |
Output is correct |
31 |
Correct |
54 ms |
11828 KB |
Output is correct |
32 |
Correct |
426 ms |
350624 KB |
Output is correct |
33 |
Correct |
176 ms |
131640 KB |
Output is correct |
34 |
Correct |
378 ms |
347592 KB |
Output is correct |
35 |
Correct |
264 ms |
193528 KB |
Output is correct |
36 |
Correct |
400 ms |
350616 KB |
Output is correct |
37 |
Correct |
347 ms |
331212 KB |
Output is correct |
38 |
Correct |
460 ms |
332644 KB |
Output is correct |
39 |
Correct |
401 ms |
330384 KB |
Output is correct |
40 |
Correct |
408 ms |
333996 KB |
Output is correct |
41 |
Correct |
377 ms |
331360 KB |
Output is correct |
42 |
Correct |
378 ms |
333300 KB |
Output is correct |
43 |
Correct |
350 ms |
329388 KB |
Output is correct |
44 |
Correct |
383 ms |
334008 KB |
Output is correct |
45 |
Correct |
317 ms |
332540 KB |
Output is correct |
46 |
Correct |
382 ms |
334028 KB |
Output is correct |
47 |
Correct |
351 ms |
329012 KB |
Output is correct |
48 |
Correct |
420 ms |
333372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
77 ms |
6412 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1364 KB |
Output is correct |
2 |
Correct |
10 ms |
8076 KB |
Output is correct |
3 |
Correct |
4 ms |
4820 KB |
Output is correct |
4 |
Correct |
7 ms |
8008 KB |
Output is correct |
5 |
Correct |
4 ms |
5824 KB |
Output is correct |
6 |
Correct |
10 ms |
8076 KB |
Output is correct |
7 |
Correct |
8 ms |
6848 KB |
Output is correct |
8 |
Correct |
6 ms |
8000 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
6 ms |
8020 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
9 ms |
8004 KB |
Output is correct |
13 |
Correct |
4 ms |
5588 KB |
Output is correct |
14 |
Correct |
4 ms |
5716 KB |
Output is correct |
15 |
Correct |
4 ms |
5600 KB |
Output is correct |
16 |
Correct |
6 ms |
5708 KB |
Output is correct |
17 |
Correct |
4 ms |
5888 KB |
Output is correct |
18 |
Correct |
6 ms |
5588 KB |
Output is correct |
19 |
Correct |
5 ms |
5716 KB |
Output is correct |
20 |
Correct |
6 ms |
5796 KB |
Output is correct |
21 |
Correct |
6 ms |
5588 KB |
Output is correct |
22 |
Correct |
6 ms |
5844 KB |
Output is correct |
23 |
Correct |
5 ms |
5760 KB |
Output is correct |
24 |
Correct |
6 ms |
5736 KB |
Output is correct |
25 |
Correct |
98 ms |
69192 KB |
Output is correct |
26 |
Correct |
374 ms |
345224 KB |
Output is correct |
27 |
Correct |
333 ms |
238020 KB |
Output is correct |
28 |
Correct |
402 ms |
350720 KB |
Output is correct |
29 |
Correct |
148 ms |
83904 KB |
Output is correct |
30 |
Correct |
389 ms |
348616 KB |
Output is correct |
31 |
Correct |
54 ms |
11828 KB |
Output is correct |
32 |
Correct |
426 ms |
350624 KB |
Output is correct |
33 |
Correct |
176 ms |
131640 KB |
Output is correct |
34 |
Correct |
378 ms |
347592 KB |
Output is correct |
35 |
Correct |
264 ms |
193528 KB |
Output is correct |
36 |
Correct |
400 ms |
350616 KB |
Output is correct |
37 |
Correct |
347 ms |
331212 KB |
Output is correct |
38 |
Correct |
460 ms |
332644 KB |
Output is correct |
39 |
Correct |
401 ms |
330384 KB |
Output is correct |
40 |
Correct |
408 ms |
333996 KB |
Output is correct |
41 |
Correct |
377 ms |
331360 KB |
Output is correct |
42 |
Correct |
378 ms |
333300 KB |
Output is correct |
43 |
Correct |
350 ms |
329388 KB |
Output is correct |
44 |
Correct |
383 ms |
334008 KB |
Output is correct |
45 |
Correct |
317 ms |
332540 KB |
Output is correct |
46 |
Correct |
382 ms |
334028 KB |
Output is correct |
47 |
Correct |
351 ms |
329012 KB |
Output is correct |
48 |
Correct |
420 ms |
333372 KB |
Output is correct |
49 |
Incorrect |
77 ms |
6412 KB |
Output isn't correct |
50 |
Halted |
0 ms |
0 KB |
- |