#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
struct tower{
ll h;
ll a,b;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin >> n;
vector <tower> arr(n+1);
vector <vector<ll>> d(n+1,vector<ll>(n+1,-1));
for (int z=0;z<n;z++){
tower temp;
cin >> temp.h >> temp.a >> temp.b;
arr[z+1] = temp;
}
for (int x=1;x<=n;x++){
ll ans = -1;
for (int y=x+arr[x].a ; y<=n && y <= x+arr[x].b;y++){
if ( y <= x + arr[x].b && y >= x + arr[x].a &&
x >= y - arr[y].b && x <= y - arr[y].a)
ans = max(ans,abs(arr[x].h-arr[y].h));
d[x][y] = ans;
}
}
for (int x=n;x>-1;x--){
for (int y=n-1;y>-1;y--){
d[y][x] = max(d[y][x],d[y+1][x]);
}
}
for (int x=0;x<=n;x++){
for (int y=1;y<=n;y++){
d[x][y] = max(d[x][y],d[x][y-1]);
}
}
// for (int z=1;z<=n;z++){
// for (int x=1;x<=n;x++){
// cout << d[z][x] << ",";
// }
// cout << endl;
// }
ll q;
cin >> q;
for (int z=0;z<q;z++){
ll a,b;
cin >> a >> b;
cout << d[a][b] << endl;
}
cin >> q;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
1024 KB |
Output is correct |
3 |
Correct |
4 ms |
896 KB |
Output is correct |
4 |
Correct |
5 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
896 KB |
Output is correct |
6 |
Correct |
3 ms |
1024 KB |
Output is correct |
7 |
Correct |
4 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
1152 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
1152 KB |
Output is correct |
11 |
Correct |
3 ms |
304 KB |
Output is correct |
12 |
Correct |
5 ms |
1024 KB |
Output is correct |
13 |
Correct |
3 ms |
896 KB |
Output is correct |
14 |
Correct |
3 ms |
896 KB |
Output is correct |
15 |
Correct |
3 ms |
896 KB |
Output is correct |
16 |
Correct |
3 ms |
896 KB |
Output is correct |
17 |
Correct |
3 ms |
896 KB |
Output is correct |
18 |
Correct |
3 ms |
896 KB |
Output is correct |
19 |
Correct |
3 ms |
896 KB |
Output is correct |
20 |
Correct |
3 ms |
896 KB |
Output is correct |
21 |
Correct |
3 ms |
896 KB |
Output is correct |
22 |
Correct |
4 ms |
896 KB |
Output is correct |
23 |
Correct |
4 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
1024 KB |
Output is correct |
3 |
Correct |
4 ms |
896 KB |
Output is correct |
4 |
Correct |
5 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
896 KB |
Output is correct |
6 |
Correct |
3 ms |
1024 KB |
Output is correct |
7 |
Correct |
4 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
1152 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
1152 KB |
Output is correct |
11 |
Correct |
3 ms |
304 KB |
Output is correct |
12 |
Correct |
5 ms |
1024 KB |
Output is correct |
13 |
Correct |
3 ms |
896 KB |
Output is correct |
14 |
Correct |
3 ms |
896 KB |
Output is correct |
15 |
Correct |
3 ms |
896 KB |
Output is correct |
16 |
Correct |
3 ms |
896 KB |
Output is correct |
17 |
Correct |
3 ms |
896 KB |
Output is correct |
18 |
Correct |
3 ms |
896 KB |
Output is correct |
19 |
Correct |
3 ms |
896 KB |
Output is correct |
20 |
Correct |
3 ms |
896 KB |
Output is correct |
21 |
Correct |
3 ms |
896 KB |
Output is correct |
22 |
Correct |
4 ms |
896 KB |
Output is correct |
23 |
Correct |
4 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
25 |
Correct |
263 ms |
7508 KB |
Output is correct |
26 |
Correct |
108 ms |
31864 KB |
Output is correct |
27 |
Correct |
380 ms |
23376 KB |
Output is correct |
28 |
Correct |
428 ms |
33584 KB |
Output is correct |
29 |
Correct |
278 ms |
9156 KB |
Output is correct |
30 |
Correct |
349 ms |
33020 KB |
Output is correct |
31 |
Correct |
436 ms |
2424 KB |
Output is correct |
32 |
Correct |
492 ms |
33792 KB |
Output is correct |
33 |
Correct |
418 ms |
13560 KB |
Output is correct |
34 |
Correct |
266 ms |
32592 KB |
Output is correct |
35 |
Correct |
457 ms |
19400 KB |
Output is correct |
36 |
Correct |
491 ms |
33656 KB |
Output is correct |
37 |
Correct |
276 ms |
30712 KB |
Output is correct |
38 |
Correct |
472 ms |
31224 KB |
Output is correct |
39 |
Correct |
132 ms |
30584 KB |
Output is correct |
40 |
Correct |
427 ms |
31224 KB |
Output is correct |
41 |
Correct |
355 ms |
30888 KB |
Output is correct |
42 |
Correct |
459 ms |
31136 KB |
Output is correct |
43 |
Correct |
200 ms |
30584 KB |
Output is correct |
44 |
Correct |
570 ms |
31352 KB |
Output is correct |
45 |
Correct |
163 ms |
30712 KB |
Output is correct |
46 |
Correct |
478 ms |
31224 KB |
Output is correct |
47 |
Correct |
181 ms |
30468 KB |
Output is correct |
48 |
Correct |
466 ms |
31224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
484 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
1024 KB |
Output is correct |
3 |
Correct |
4 ms |
896 KB |
Output is correct |
4 |
Correct |
5 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
896 KB |
Output is correct |
6 |
Correct |
3 ms |
1024 KB |
Output is correct |
7 |
Correct |
4 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
1152 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
1152 KB |
Output is correct |
11 |
Correct |
3 ms |
304 KB |
Output is correct |
12 |
Correct |
5 ms |
1024 KB |
Output is correct |
13 |
Correct |
3 ms |
896 KB |
Output is correct |
14 |
Correct |
3 ms |
896 KB |
Output is correct |
15 |
Correct |
3 ms |
896 KB |
Output is correct |
16 |
Correct |
3 ms |
896 KB |
Output is correct |
17 |
Correct |
3 ms |
896 KB |
Output is correct |
18 |
Correct |
3 ms |
896 KB |
Output is correct |
19 |
Correct |
3 ms |
896 KB |
Output is correct |
20 |
Correct |
3 ms |
896 KB |
Output is correct |
21 |
Correct |
3 ms |
896 KB |
Output is correct |
22 |
Correct |
4 ms |
896 KB |
Output is correct |
23 |
Correct |
4 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
25 |
Correct |
263 ms |
7508 KB |
Output is correct |
26 |
Correct |
108 ms |
31864 KB |
Output is correct |
27 |
Correct |
380 ms |
23376 KB |
Output is correct |
28 |
Correct |
428 ms |
33584 KB |
Output is correct |
29 |
Correct |
278 ms |
9156 KB |
Output is correct |
30 |
Correct |
349 ms |
33020 KB |
Output is correct |
31 |
Correct |
436 ms |
2424 KB |
Output is correct |
32 |
Correct |
492 ms |
33792 KB |
Output is correct |
33 |
Correct |
418 ms |
13560 KB |
Output is correct |
34 |
Correct |
266 ms |
32592 KB |
Output is correct |
35 |
Correct |
457 ms |
19400 KB |
Output is correct |
36 |
Correct |
491 ms |
33656 KB |
Output is correct |
37 |
Correct |
276 ms |
30712 KB |
Output is correct |
38 |
Correct |
472 ms |
31224 KB |
Output is correct |
39 |
Correct |
132 ms |
30584 KB |
Output is correct |
40 |
Correct |
427 ms |
31224 KB |
Output is correct |
41 |
Correct |
355 ms |
30888 KB |
Output is correct |
42 |
Correct |
459 ms |
31136 KB |
Output is correct |
43 |
Correct |
200 ms |
30584 KB |
Output is correct |
44 |
Correct |
570 ms |
31352 KB |
Output is correct |
45 |
Correct |
163 ms |
30712 KB |
Output is correct |
46 |
Correct |
478 ms |
31224 KB |
Output is correct |
47 |
Correct |
181 ms |
30468 KB |
Output is correct |
48 |
Correct |
466 ms |
31224 KB |
Output is correct |
49 |
Runtime error |
484 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
50 |
Halted |
0 ms |
0 KB |
- |