# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
299654 |
2020-09-15T11:53:19 Z |
pit4h |
Triple Jump (JOI19_jumps) |
C++14 |
|
1742 ms |
90452 KB |
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
const int N = 5e5+1;
int n, q, ans[N];
vector<pii> queries[N], vec[N];
struct Segtree {
vector<int> node, push, max_in_range;
int base;
void init(int sz, vector<int> leaves) {
base = 1;
while(base < sz) base *= 2;
node.resize(2*base+1);
push.resize(2*base+1);
max_in_range.resize(2*base+1);
for(int i=0; i<(int)leaves.size(); ++i) {
max_in_range[i+base] = leaves[i];
}
for(int i=base-1; i>=1; --i) {
max_in_range[i] = max(max_in_range[i*2], max_in_range[i*2+1]);
}
}
void Push(int x, int y) {
node[y] = max(node[y], push[x] + max_in_range[y]);
push[y] = max(push[y], push[x]);
}
void ins(int l, int r, int val, int id, int L, int R) {
if(l > R || r < L) return;
if(L>=l && R<=r) {
node[id] = max(node[id], val + max_in_range[id]);
push[id] = max(push[id], val);
return;
}
int M = (L+R)/2;
Push(id, id*2); Push(id, id*2+1);
ins(l, r, val, id*2, L, M);
ins(l, r, val, id*2+1, M+1, R);
node[id] = max(node[id*2], node[id*2+1]);
}
int qry(int l, int r, int id, int L, int R) {
if(l > R || r < L) return 0;
if(L>=l && R<=r) {
return node[id];
}
int M = (L+R)/2;
Push(id, id*2); Push(id, id*2+1);
int res = max(qry(l, r, id*2, L, M), qry(l, r, id*2+1, M+1, R));
node[id] = max(node[id*2], node[id*2+1]);
return res;
}
};
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
vector<int> a(n);
for(int i=0; i<n; ++i) {
cin>>a[i];
}
Segtree tree;
tree.init(n, a);
cin>>q;
for(int i=0; i<q; ++i) {
int l, r; cin>>l>>r;
queries[l-1].push_back(mp(r-1, i));
}
vector<int> mono;
for(int i=0; i<n; ++i) {
while(mono.size() && a[mono.back()] <= a[i]) {
vec[mono.back()].push_back(mp(a[i] + a[mono.back()], i+(i-mono.back())));
mono.pop_back();
}
if(mono.size()) {
vec[mono.back()].push_back(mp(a[i] + a[mono.back()], i+(i-mono.back())));
}
mono.push_back(i);
}
for(int i=n-1; i>=0; --i) {
for(auto j: vec[i]) {
if(j.nd > n-1) continue;
tree.ins(j.nd, n-1, j.st, 1, 0, tree.base-1);
}
for(auto j: queries[i]) {
ans[j.nd] = tree.qry(i, j.st, 1, 0, tree.base-1);
}
}
for(int i=0; i<q; ++i) {
cout<<ans[i]<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23808 KB |
Output is correct |
2 |
Correct |
17 ms |
23808 KB |
Output is correct |
3 |
Correct |
17 ms |
23808 KB |
Output is correct |
4 |
Correct |
17 ms |
23808 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23808 KB |
Output is correct |
7 |
Correct |
17 ms |
23808 KB |
Output is correct |
8 |
Correct |
17 ms |
23808 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
16 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23808 KB |
Output is correct |
2 |
Correct |
17 ms |
23808 KB |
Output is correct |
3 |
Correct |
17 ms |
23808 KB |
Output is correct |
4 |
Correct |
17 ms |
23808 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23808 KB |
Output is correct |
7 |
Correct |
17 ms |
23808 KB |
Output is correct |
8 |
Correct |
17 ms |
23808 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
16 ms |
23808 KB |
Output is correct |
11 |
Correct |
396 ms |
42232 KB |
Output is correct |
12 |
Correct |
400 ms |
42104 KB |
Output is correct |
13 |
Correct |
393 ms |
42104 KB |
Output is correct |
14 |
Correct |
396 ms |
42104 KB |
Output is correct |
15 |
Correct |
397 ms |
42108 KB |
Output is correct |
16 |
Correct |
408 ms |
41464 KB |
Output is correct |
17 |
Correct |
391 ms |
41464 KB |
Output is correct |
18 |
Correct |
398 ms |
41464 KB |
Output is correct |
19 |
Correct |
393 ms |
41980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
313 ms |
40168 KB |
Output is correct |
2 |
Correct |
179 ms |
38888 KB |
Output is correct |
3 |
Correct |
176 ms |
39656 KB |
Output is correct |
4 |
Correct |
308 ms |
40040 KB |
Output is correct |
5 |
Correct |
315 ms |
40040 KB |
Output is correct |
6 |
Correct |
308 ms |
39528 KB |
Output is correct |
7 |
Correct |
314 ms |
39272 KB |
Output is correct |
8 |
Correct |
314 ms |
39272 KB |
Output is correct |
9 |
Correct |
308 ms |
39784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23808 KB |
Output is correct |
2 |
Correct |
17 ms |
23808 KB |
Output is correct |
3 |
Correct |
17 ms |
23808 KB |
Output is correct |
4 |
Correct |
17 ms |
23808 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23808 KB |
Output is correct |
7 |
Correct |
17 ms |
23808 KB |
Output is correct |
8 |
Correct |
17 ms |
23808 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
16 ms |
23808 KB |
Output is correct |
11 |
Correct |
396 ms |
42232 KB |
Output is correct |
12 |
Correct |
400 ms |
42104 KB |
Output is correct |
13 |
Correct |
393 ms |
42104 KB |
Output is correct |
14 |
Correct |
396 ms |
42104 KB |
Output is correct |
15 |
Correct |
397 ms |
42108 KB |
Output is correct |
16 |
Correct |
408 ms |
41464 KB |
Output is correct |
17 |
Correct |
391 ms |
41464 KB |
Output is correct |
18 |
Correct |
398 ms |
41464 KB |
Output is correct |
19 |
Correct |
393 ms |
41980 KB |
Output is correct |
20 |
Correct |
313 ms |
40168 KB |
Output is correct |
21 |
Correct |
179 ms |
38888 KB |
Output is correct |
22 |
Correct |
176 ms |
39656 KB |
Output is correct |
23 |
Correct |
308 ms |
40040 KB |
Output is correct |
24 |
Correct |
315 ms |
40040 KB |
Output is correct |
25 |
Correct |
308 ms |
39528 KB |
Output is correct |
26 |
Correct |
314 ms |
39272 KB |
Output is correct |
27 |
Correct |
314 ms |
39272 KB |
Output is correct |
28 |
Correct |
308 ms |
39784 KB |
Output is correct |
29 |
Correct |
1695 ms |
84676 KB |
Output is correct |
30 |
Correct |
1349 ms |
81620 KB |
Output is correct |
31 |
Correct |
1357 ms |
83540 KB |
Output is correct |
32 |
Correct |
1742 ms |
84704 KB |
Output is correct |
33 |
Correct |
1719 ms |
84804 KB |
Output is correct |
34 |
Correct |
1718 ms |
82516 KB |
Output is correct |
35 |
Correct |
1698 ms |
82132 KB |
Output is correct |
36 |
Correct |
1682 ms |
82148 KB |
Output is correct |
37 |
Correct |
1704 ms |
83572 KB |
Output is correct |
38 |
Correct |
1324 ms |
90452 KB |
Output is correct |
39 |
Correct |
1311 ms |
90444 KB |
Output is correct |
40 |
Correct |
1283 ms |
87272 KB |
Output is correct |
41 |
Correct |
1297 ms |
86572 KB |
Output is correct |
42 |
Correct |
1322 ms |
86644 KB |
Output is correct |
43 |
Correct |
1323 ms |
88444 KB |
Output is correct |
44 |
Correct |
1414 ms |
89976 KB |
Output is correct |
45 |
Correct |
1533 ms |
89940 KB |
Output is correct |
46 |
Correct |
1440 ms |
86648 KB |
Output is correct |
47 |
Correct |
1371 ms |
86480 KB |
Output is correct |
48 |
Correct |
1410 ms |
86180 KB |
Output is correct |
49 |
Correct |
1388 ms |
88252 KB |
Output is correct |
50 |
Correct |
1493 ms |
87708 KB |
Output is correct |
51 |
Correct |
1506 ms |
87824 KB |
Output is correct |
52 |
Correct |
1496 ms |
85204 KB |
Output is correct |
53 |
Correct |
1538 ms |
84976 KB |
Output is correct |
54 |
Correct |
1451 ms |
85044 KB |
Output is correct |
55 |
Correct |
1473 ms |
86668 KB |
Output is correct |