# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
296873 |
2020-09-11T03:20:04 Z |
YJU |
Triple Jump (JOI19_jumps) |
C++14 |
|
1492 ms |
126696 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
ll seg[4*N],tag[4*N],n,u[N],m,lst,ans[N],pseg[4*N];
vector<pll> upd[N];
pair<pll,ll> q[N];
stack<pll> stk;
void push(ll id){
tag[id*2]=max(tag[id*2],tag[id]);
tag[id*2+1]=max(tag[id*2+1],tag[id]);
seg[id*2]=max(seg[id*2],pseg[id*2]+tag[id*2]);seg[id*2+1]=max(seg[id*2+1],pseg[id*2+1]+tag[id*2+1]);
}
void add(ll id,ll l,ll r,ll ql,ll qr,ll D){
if(l>=ql&&r<=qr){
tag[id]=max(tag[id],D);
push(id);
seg[id]=max(seg[id*2],seg[id*2+1]);
seg[id]=max(seg[id],pseg[id]+tag[id]);
//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
return ;
}
if(l>=qr||r<=ql)return ;
push(id);
ll mid=(l+r)/2;
add(id*2,l,mid,ql,qr,D);
add(id*2+1,mid,r,ql,qr,D);
seg[id]=max(seg[id*2],seg[id*2+1]);
//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
}
void pins(ll id,ll l,ll r,ll to,ll D){
if(l==r-1){pseg[id]=max(pseg[id],D);return ;}
ll mid=(l+r)/2;
if(to<mid){
pins(id*2,l,mid,to,D);
}else{
pins(id*2+1,mid,r,to,D);
}
pseg[id]=max(pseg[id*2],pseg[id*2+1]);
}
ll Q(ll id,ll l,ll r,ll ql,ll qr){
//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
if(l>=ql&&r<=qr)return seg[id];
if(l>=qr||r<=ql)return 0;
push(id);
ll mid=(l+r)/2;
return max(Q(id*2,l,mid,ql,qr),Q(id*2+1,mid,r,ql,qr));
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
lst=n;
REP1(i,n)cin>>u[i],pins(1,1,n+1,i,u[i]);
REP1(i,n){
while(SZ(stk)&&stk.top().X<=u[i]){
upd[stk.top().Y].pb(mp(i,stk.top().X+u[i]));
stk.pop();
}
if(SZ(stk)){upd[stk.top().Y].pb(mp(i,stk.top().X+u[i]));}
stk.push(mp(u[i],i));
}
cin>>m;
REP(i,m)cin>>q[i].X.X>>q[i].X.Y,q[i].Y=i;
sort(q,q+m,[](pair<pll,ll> A,pair<pll,ll> B){
return (A.X.X>B.X.X);
});
REP(i,m){
//cout<<"que : "<<q[i].X.X<<" "<<q[i].X.Y<<"\n";
while(lst>=q[i].X.X){
for(auto j:upd[lst]){
if(j.X+j.X-lst>=n+1)continue;
//cout<<"upd : "<<j.X<<" "<<2*j.X-lst<<" "<<j.Y<<"\n";
add(1,1,n+1,2*j.X-lst,n+1,j.Y);
}
--lst;
}
ans[q[i].Y]=Q(1,1,n+1,q[i].X.X+2,q[i].X.Y+1);
}
REP(i,m)cout<<ans[i]<<"\n";
return 0;
}
/*
5
5 2 1 5 3
3
1 5
2 5
1 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23808 KB |
Output is correct |
2 |
Correct |
16 ms |
23936 KB |
Output is correct |
3 |
Correct |
15 ms |
24064 KB |
Output is correct |
4 |
Correct |
15 ms |
23936 KB |
Output is correct |
5 |
Correct |
15 ms |
23936 KB |
Output is correct |
6 |
Correct |
15 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23808 KB |
Output is correct |
8 |
Correct |
15 ms |
23808 KB |
Output is correct |
9 |
Correct |
15 ms |
23936 KB |
Output is correct |
10 |
Correct |
15 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23808 KB |
Output is correct |
2 |
Correct |
16 ms |
23936 KB |
Output is correct |
3 |
Correct |
15 ms |
24064 KB |
Output is correct |
4 |
Correct |
15 ms |
23936 KB |
Output is correct |
5 |
Correct |
15 ms |
23936 KB |
Output is correct |
6 |
Correct |
15 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23808 KB |
Output is correct |
8 |
Correct |
15 ms |
23808 KB |
Output is correct |
9 |
Correct |
15 ms |
23936 KB |
Output is correct |
10 |
Correct |
15 ms |
23808 KB |
Output is correct |
11 |
Correct |
421 ms |
50296 KB |
Output is correct |
12 |
Correct |
406 ms |
50168 KB |
Output is correct |
13 |
Correct |
399 ms |
50040 KB |
Output is correct |
14 |
Correct |
402 ms |
50168 KB |
Output is correct |
15 |
Correct |
407 ms |
50424 KB |
Output is correct |
16 |
Correct |
410 ms |
49788 KB |
Output is correct |
17 |
Correct |
401 ms |
49492 KB |
Output is correct |
18 |
Correct |
404 ms |
49528 KB |
Output is correct |
19 |
Correct |
406 ms |
50168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
290 ms |
57936 KB |
Output is correct |
2 |
Correct |
172 ms |
53884 KB |
Output is correct |
3 |
Correct |
176 ms |
57208 KB |
Output is correct |
4 |
Correct |
276 ms |
57976 KB |
Output is correct |
5 |
Correct |
275 ms |
57976 KB |
Output is correct |
6 |
Correct |
272 ms |
57464 KB |
Output is correct |
7 |
Correct |
278 ms |
57212 KB |
Output is correct |
8 |
Correct |
269 ms |
57208 KB |
Output is correct |
9 |
Correct |
274 ms |
57464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23808 KB |
Output is correct |
2 |
Correct |
16 ms |
23936 KB |
Output is correct |
3 |
Correct |
15 ms |
24064 KB |
Output is correct |
4 |
Correct |
15 ms |
23936 KB |
Output is correct |
5 |
Correct |
15 ms |
23936 KB |
Output is correct |
6 |
Correct |
15 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23808 KB |
Output is correct |
8 |
Correct |
15 ms |
23808 KB |
Output is correct |
9 |
Correct |
15 ms |
23936 KB |
Output is correct |
10 |
Correct |
15 ms |
23808 KB |
Output is correct |
11 |
Correct |
421 ms |
50296 KB |
Output is correct |
12 |
Correct |
406 ms |
50168 KB |
Output is correct |
13 |
Correct |
399 ms |
50040 KB |
Output is correct |
14 |
Correct |
402 ms |
50168 KB |
Output is correct |
15 |
Correct |
407 ms |
50424 KB |
Output is correct |
16 |
Correct |
410 ms |
49788 KB |
Output is correct |
17 |
Correct |
401 ms |
49492 KB |
Output is correct |
18 |
Correct |
404 ms |
49528 KB |
Output is correct |
19 |
Correct |
406 ms |
50168 KB |
Output is correct |
20 |
Correct |
290 ms |
57936 KB |
Output is correct |
21 |
Correct |
172 ms |
53884 KB |
Output is correct |
22 |
Correct |
176 ms |
57208 KB |
Output is correct |
23 |
Correct |
276 ms |
57976 KB |
Output is correct |
24 |
Correct |
275 ms |
57976 KB |
Output is correct |
25 |
Correct |
272 ms |
57464 KB |
Output is correct |
26 |
Correct |
278 ms |
57212 KB |
Output is correct |
27 |
Correct |
269 ms |
57208 KB |
Output is correct |
28 |
Correct |
274 ms |
57464 KB |
Output is correct |
29 |
Correct |
1492 ms |
126200 KB |
Output is correct |
30 |
Correct |
1180 ms |
116088 KB |
Output is correct |
31 |
Correct |
1186 ms |
124376 KB |
Output is correct |
32 |
Correct |
1461 ms |
126456 KB |
Output is correct |
33 |
Correct |
1481 ms |
126172 KB |
Output is correct |
34 |
Correct |
1463 ms |
123896 KB |
Output is correct |
35 |
Correct |
1447 ms |
123768 KB |
Output is correct |
36 |
Correct |
1455 ms |
123640 KB |
Output is correct |
37 |
Correct |
1466 ms |
125088 KB |
Output is correct |
38 |
Correct |
1148 ms |
126248 KB |
Output is correct |
39 |
Correct |
1144 ms |
126328 KB |
Output is correct |
40 |
Correct |
1138 ms |
123044 KB |
Output is correct |
41 |
Correct |
1142 ms |
122364 KB |
Output is correct |
42 |
Correct |
1145 ms |
122488 KB |
Output is correct |
43 |
Correct |
1155 ms |
124280 KB |
Output is correct |
44 |
Correct |
1211 ms |
126328 KB |
Output is correct |
45 |
Correct |
1211 ms |
126224 KB |
Output is correct |
46 |
Correct |
1190 ms |
123128 KB |
Output is correct |
47 |
Correct |
1179 ms |
122744 KB |
Output is correct |
48 |
Correct |
1186 ms |
122744 KB |
Output is correct |
49 |
Correct |
1212 ms |
124624 KB |
Output is correct |
50 |
Correct |
1281 ms |
126696 KB |
Output is correct |
51 |
Correct |
1268 ms |
126584 KB |
Output is correct |
52 |
Correct |
1272 ms |
123880 KB |
Output is correct |
53 |
Correct |
1254 ms |
123496 KB |
Output is correct |
54 |
Correct |
1273 ms |
123372 KB |
Output is correct |
55 |
Correct |
1257 ms |
125248 KB |
Output is correct |