# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
946394 |
2024-03-14T15:47:21 Z |
siewjh |
Triple Jump (JOI19_jumps) |
C++17 |
|
693 ms |
117952 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int inf = 1e9;
int vec[MAXN];
struct node{
int s, e, m, ab, c, abc, lazy;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1, ab = 0, abc = 0, lazy = 0;
if (s == e) c = vec[s];
else{
l = new node(s, m);
r = new node(m + 1, e);
c = max(l->c, r->c);
}
}
void push(int v){
if (v <= ab) return;
ab = v; abc = max(abc, ab + c);
lazy = v;
}
void propo(){
if (s == e) return;
if (lazy != 0){
l->push(lazy); r->push(lazy);
lazy = 0;
}
}
void update(int x, int y, int v){
if (x > y) return;
if (x == s && y == e){
push(v); return;
}
propo();
if (y <= m) l->update(x, y, v);
else if (x > m) r->update(x, y, v);
else{
l->update(x, m, v); r->update(m + 1, y, v);
}
propo();
abc = max(l->abc, r->abc);
}
int query(int x, int y){
if (x == s && y == e) return abc;
propo();
if (y <= m) return l->query(x, y);
else if (x > m) return r->query(x, y);
else return max(l->query(x, m), r->query(m + 1, y));
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int nums; cin >> nums;
vector<int> st;
vector<vector<int>> abp(nums + 1);
for (int i = 1; i <= nums; i++){
cin >> vec[i];
while (!st.empty() && vec[st.back()] < vec[i]){
abp[st.back()].push_back(i);
st.pop_back();
}
if (!st.empty()){
abp[st.back()].push_back(i);
if (vec[st.back()] == vec[i]) st.pop_back();
}
st.push_back(i);
}
int queries; cin >> queries;
vector<tuple<int, int, int>> qvec(queries);
vector<int> ans(queries);
for (int q = 0; q < queries; q++){
int l, r; cin >> l >> r;
qvec[q] = {l, r, q};
}
sort(qvec.begin(), qvec.end(), greater<tuple<int, int, int>>());
node *root = new node(1, nums);
int ca = nums + 1;
for (auto &[l, r, q] : qvec){
while (ca > l){
ca--;
for (int b : abp[ca]) root->update(2 * b - ca, nums, vec[ca] + vec[b]);
}
ans[q] = root->query(l, r);
}
for (int x : ans) cout << x << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
187 ms |
18760 KB |
Output is correct |
12 |
Correct |
184 ms |
18664 KB |
Output is correct |
13 |
Correct |
206 ms |
18784 KB |
Output is correct |
14 |
Correct |
187 ms |
18932 KB |
Output is correct |
15 |
Correct |
191 ms |
18932 KB |
Output is correct |
16 |
Correct |
188 ms |
18056 KB |
Output is correct |
17 |
Correct |
199 ms |
18084 KB |
Output is correct |
18 |
Correct |
189 ms |
18140 KB |
Output is correct |
19 |
Correct |
188 ms |
18772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
39124 KB |
Output is correct |
2 |
Correct |
63 ms |
38740 KB |
Output is correct |
3 |
Correct |
66 ms |
39628 KB |
Output is correct |
4 |
Correct |
104 ms |
38992 KB |
Output is correct |
5 |
Correct |
105 ms |
38996 KB |
Output is correct |
6 |
Correct |
100 ms |
38476 KB |
Output is correct |
7 |
Correct |
100 ms |
38224 KB |
Output is correct |
8 |
Correct |
99 ms |
38284 KB |
Output is correct |
9 |
Correct |
100 ms |
38588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
187 ms |
18760 KB |
Output is correct |
12 |
Correct |
184 ms |
18664 KB |
Output is correct |
13 |
Correct |
206 ms |
18784 KB |
Output is correct |
14 |
Correct |
187 ms |
18932 KB |
Output is correct |
15 |
Correct |
191 ms |
18932 KB |
Output is correct |
16 |
Correct |
188 ms |
18056 KB |
Output is correct |
17 |
Correct |
199 ms |
18084 KB |
Output is correct |
18 |
Correct |
189 ms |
18140 KB |
Output is correct |
19 |
Correct |
188 ms |
18772 KB |
Output is correct |
20 |
Correct |
106 ms |
39124 KB |
Output is correct |
21 |
Correct |
63 ms |
38740 KB |
Output is correct |
22 |
Correct |
66 ms |
39628 KB |
Output is correct |
23 |
Correct |
104 ms |
38992 KB |
Output is correct |
24 |
Correct |
105 ms |
38996 KB |
Output is correct |
25 |
Correct |
100 ms |
38476 KB |
Output is correct |
26 |
Correct |
100 ms |
38224 KB |
Output is correct |
27 |
Correct |
99 ms |
38284 KB |
Output is correct |
28 |
Correct |
100 ms |
38588 KB |
Output is correct |
29 |
Correct |
693 ms |
116724 KB |
Output is correct |
30 |
Correct |
552 ms |
116048 KB |
Output is correct |
31 |
Correct |
600 ms |
117952 KB |
Output is correct |
32 |
Correct |
671 ms |
116744 KB |
Output is correct |
33 |
Correct |
674 ms |
116788 KB |
Output is correct |
34 |
Correct |
668 ms |
114436 KB |
Output is correct |
35 |
Correct |
690 ms |
114076 KB |
Output is correct |
36 |
Correct |
667 ms |
114156 KB |
Output is correct |
37 |
Correct |
663 ms |
115708 KB |
Output is correct |
38 |
Correct |
475 ms |
116632 KB |
Output is correct |
39 |
Correct |
455 ms |
116564 KB |
Output is correct |
40 |
Correct |
464 ms |
113504 KB |
Output is correct |
41 |
Correct |
465 ms |
112792 KB |
Output is correct |
42 |
Correct |
461 ms |
112944 KB |
Output is correct |
43 |
Correct |
449 ms |
114540 KB |
Output is correct |
44 |
Correct |
479 ms |
116816 KB |
Output is correct |
45 |
Correct |
491 ms |
116788 KB |
Output is correct |
46 |
Correct |
503 ms |
113488 KB |
Output is correct |
47 |
Correct |
470 ms |
113236 KB |
Output is correct |
48 |
Correct |
462 ms |
113236 KB |
Output is correct |
49 |
Correct |
506 ms |
115284 KB |
Output is correct |
50 |
Correct |
527 ms |
116904 KB |
Output is correct |
51 |
Correct |
530 ms |
116820 KB |
Output is correct |
52 |
Correct |
565 ms |
114256 KB |
Output is correct |
53 |
Correct |
514 ms |
114108 KB |
Output is correct |
54 |
Correct |
521 ms |
114024 KB |
Output is correct |
55 |
Correct |
513 ms |
115536 KB |
Output is correct |