# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
206720 |
2020-03-04T17:48:53 Z |
laoriu |
Triple Jump (JOI19_jumps) |
C++14 |
|
1136 ms |
83412 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pp;
int n,A[500002],q;
vector <pp> P;
struct query
{
int l,r,pos;
bool operator < (const query&a)
const
{
return (l>a.l);
}
};
query Q[500002];
long long res[500002];
struct node
{
long long a,val,vmax;
};
node it[2000002];
void build(int id,int l,int r)
{
if (l==r)
{
it[id].a=A[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
it[id].a=max(it[id*2].a,it[id*2+1].a);
}
void down(int id)
{
long long t=it[id].vmax;
it[id*2].vmax=max(it[id*2].vmax,t);it[id*2].val=max(it[id*2].val,it[id*2].a+t);
it[id*2+1].vmax=max(it[id*2+1].vmax,t);it[id*2+1].val=max(it[id*2+1].val,it[id*2+1].a+t);
}
void update(int id,int l,int r,int a,int b,long long val)
{
if (l>b||r<a) return;
if (l>=a&&r<=b)
{
it[id].vmax=max(it[id].vmax,val);
it[id].val=max(it[id].val,it[id].a+val);
return;
}
down(id);
int mid=(l+r)/2;
update(id*2,l,mid,a,b,val);
update(id*2+1,mid+1,r,a,b,val);
it[id].val=max(it[id*2].val,it[id*2+1].val);
}
long long query(int id,int l,int r,int a,int b)
{
if (l>b||r<a) return 0;
if (l>=a&&r<=b) return it[id].val;
down(id);
int mid=(l+r)/2;
return max(query(id*2,l,mid,a,b),query(id*2+1,mid+1,r,a,b));
}
void prepare()
{
deque <int> dq;
for (int i=1;i<=n;i++)
{
while (!dq.empty()&&A[dq.back()]<A[i]) dq.pop_back();
if (!dq.empty()) P.push_back({dq.back(),i});
dq.push_back(i);
}
while (!dq.empty()) dq.pop_back();
for (int i=n;i>=1;i--)
{
while (!dq.empty()&&A[dq.back()]<=A[i]) dq.pop_back();
if (!dq.empty()) {P.push_back({i,dq.back()});}
dq.push_back(i);
}
sort(P.begin(),P.end(),greater<pp>());
// for (int i=0;i<P.size();i++)
// cout<<P[i].first<<' '<<P[i].second<<'\n';
}
void solve()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>A[i];
prepare();
cin>>q;
for (int i=1;i<=q;i++)
{
cin>>Q[i].l>>Q[i].r;
Q[i].pos=i;
}
for (int i=1;i<=4*n;i++) it[i].a=it[i].val=it[i].vmax=0;
build(1,1,n);
sort(Q+1,Q+q+1);
int d=0;
for (int i=1;i<=q;i++)
{
while (d<P.size()&&P[d].first>=Q[i].l)
{
int c=2*P[d].second-P[d].first;
if (c<=n) update(1,1,n,c,n,(long long) A[P[d].first]+A[P[d].second]);
d++;
}
res[Q[i].pos]=query(1,1,n,Q[i].l,Q[i].r);
}
for (int i=1;i<=q;i++)
cout<<res[i]<<'\n';
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("jump1000.inp","r",stdin);
// freopen("jump1000.out","w",stdout);
solve();
}
Compilation message
jumps.cpp: In function 'void solve()':
jumps.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (d<P.size()&&P[d].first>=Q[i].l)
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
248 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
248 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
347 ms |
20536 KB |
Output is correct |
12 |
Correct |
332 ms |
20472 KB |
Output is correct |
13 |
Correct |
351 ms |
20472 KB |
Output is correct |
14 |
Correct |
364 ms |
20600 KB |
Output is correct |
15 |
Correct |
327 ms |
20600 KB |
Output is correct |
16 |
Correct |
338 ms |
19960 KB |
Output is correct |
17 |
Correct |
365 ms |
20088 KB |
Output is correct |
18 |
Correct |
344 ms |
19960 KB |
Output is correct |
19 |
Correct |
350 ms |
20472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
195 ms |
24928 KB |
Output is correct |
2 |
Correct |
122 ms |
24236 KB |
Output is correct |
3 |
Correct |
99 ms |
24140 KB |
Output is correct |
4 |
Correct |
222 ms |
24880 KB |
Output is correct |
5 |
Correct |
208 ms |
24928 KB |
Output is correct |
6 |
Correct |
191 ms |
24416 KB |
Output is correct |
7 |
Correct |
188 ms |
24160 KB |
Output is correct |
8 |
Correct |
209 ms |
24288 KB |
Output is correct |
9 |
Correct |
203 ms |
24544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
248 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
347 ms |
20536 KB |
Output is correct |
12 |
Correct |
332 ms |
20472 KB |
Output is correct |
13 |
Correct |
351 ms |
20472 KB |
Output is correct |
14 |
Correct |
364 ms |
20600 KB |
Output is correct |
15 |
Correct |
327 ms |
20600 KB |
Output is correct |
16 |
Correct |
338 ms |
19960 KB |
Output is correct |
17 |
Correct |
365 ms |
20088 KB |
Output is correct |
18 |
Correct |
344 ms |
19960 KB |
Output is correct |
19 |
Correct |
350 ms |
20472 KB |
Output is correct |
20 |
Correct |
195 ms |
24928 KB |
Output is correct |
21 |
Correct |
122 ms |
24236 KB |
Output is correct |
22 |
Correct |
99 ms |
24140 KB |
Output is correct |
23 |
Correct |
222 ms |
24880 KB |
Output is correct |
24 |
Correct |
208 ms |
24928 KB |
Output is correct |
25 |
Correct |
191 ms |
24416 KB |
Output is correct |
26 |
Correct |
188 ms |
24160 KB |
Output is correct |
27 |
Correct |
209 ms |
24288 KB |
Output is correct |
28 |
Correct |
203 ms |
24544 KB |
Output is correct |
29 |
Correct |
1097 ms |
83152 KB |
Output is correct |
30 |
Correct |
911 ms |
81056 KB |
Output is correct |
31 |
Correct |
847 ms |
80936 KB |
Output is correct |
32 |
Correct |
1132 ms |
83160 KB |
Output is correct |
33 |
Correct |
1136 ms |
83156 KB |
Output is correct |
34 |
Correct |
1113 ms |
81032 KB |
Output is correct |
35 |
Correct |
1108 ms |
80540 KB |
Output is correct |
36 |
Correct |
1121 ms |
80468 KB |
Output is correct |
37 |
Correct |
1080 ms |
81876 KB |
Output is correct |
38 |
Correct |
954 ms |
83164 KB |
Output is correct |
39 |
Correct |
927 ms |
83028 KB |
Output is correct |
40 |
Correct |
919 ms |
79896 KB |
Output is correct |
41 |
Correct |
906 ms |
79188 KB |
Output is correct |
42 |
Correct |
902 ms |
79332 KB |
Output is correct |
43 |
Correct |
899 ms |
80980 KB |
Output is correct |
44 |
Correct |
969 ms |
83028 KB |
Output is correct |
45 |
Correct |
929 ms |
83112 KB |
Output is correct |
46 |
Correct |
910 ms |
79956 KB |
Output is correct |
47 |
Correct |
916 ms |
79828 KB |
Output is correct |
48 |
Correct |
915 ms |
79492 KB |
Output is correct |
49 |
Correct |
930 ms |
81620 KB |
Output is correct |
50 |
Correct |
966 ms |
83412 KB |
Output is correct |
51 |
Correct |
1000 ms |
83132 KB |
Output is correct |
52 |
Correct |
1012 ms |
80588 KB |
Output is correct |
53 |
Correct |
1020 ms |
80280 KB |
Output is correct |
54 |
Correct |
1030 ms |
80356 KB |
Output is correct |
55 |
Correct |
1064 ms |
81992 KB |
Output is correct |