Submission #1013608

#TimeUsernameProblemLanguageResultExecution timeMemory
1013608ReLiceTriple Jump (JOI19_jumps)C++17
100 / 100
940 ms119476 KiB
#include <bits/stdc++.h> #define ll long long #define str string #define ins insert #define ld long double #define pb push_back #define pf push_front #define pof pop_front() #define pob pop_back() #define lb lower_bound #define ub upper_bound #define endl "\n" #define fr first #define sc second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz size() #define vll vector<ll> #define bc back() #define arr array #define pll vector<pair<ll,ll>> using namespace std;/* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/ template<class S,class T> bool chmin(S &a,const T &b) { return a>b?(a=b)==b:false; } template<class S,class T> bool chmax(S &a,const T &b) { return a<b?(a=b)==b:false; } //void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} void start(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const ll inf=1e18; const ll mod=998244353; const ll N=5e5+7; const ld eps=1e-9; struct node{ ll ans,ab,c; node operator + (node b){ node x; x.ans=max(ans,b.ans); x.ab=max(ab,b.ab); x.c=max(c,b.c); return x; } }; vector<node> t(N*4); vll add(N*4); ll a[N]; void build(ll v,ll tl,ll tr){ if(tl==tr){ t[v]={a[tl],0ll,a[tl]}; return; } ll tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v]=t[v*2]+t[v*2+1]; } void push(ll v,ll tl,ll tr){ if(tl!=tr){ chmax(add[v*2],add[v]); chmax(add[v*2+1],add[v]); } chmax(t[v].ab,add[v]); chmax(t[v].ans,t[v].c+add[v]); add[v]=0; } void upd(ll l,ll r,ll val,ll v,ll tl,ll tr){ push(v,tl,tr); if(tl>r || tr<l)return ; if(l<=tl && tr<=r){ add[v]=val; push(v,tl,tr); return; } ll tm=(tl+tr)/2; upd(l,r,val,v*2,tl,tm); upd(l,r,val,v*2+1,tm+1,tr); t[v]=t[v]+t[v*2]; t[v]=t[v]+t[v*2+1]; } ll get(ll l,ll r,ll v,ll tl,ll tr){ push(v,tl,tr); if(tl>r || tr<l)return 0ll; if(l<=tl && tr<=r){ //cout<<tl<<' '<<tr<<endl; //cout<<t[v].ans<<' '<<t[v].ab<<' '<<t[v].c<<endl; return t[v].ans; } ll tm=(tl+tr)/2; return max(get(l,r,v*2,tl,tm),get(l,r,v*2+1,tm+1,tr)); } void solve(){ ll i,j; ll n,q; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; build(1,1,n); cin>>q; vector<pll> qq(n+5); for(i=0;i<q;i++){ ll l,r; cin>>l>>r; qq[l].pb({r,i}); } ll ans[q]; pll cur; for(i=n;i>0;i--){ while(cur.sz && cur.bc.fr<a[i]){ ll A=i,B=cur.bc.sc; //cout<<a[A]<<' '<<a[B]<<endl; if(2*B-A<=n)upd(2*B-A,n,a[i]+a[B],1,1,n); cur.pob; } if(cur.sz){ ll A=i,B=cur.bc.sc; //cout<<a[A]<<' '<<a[B]<<endl; if(2*B-A<=n)upd(2*B-A,n,a[i]+a[B],1,1,n); } cur.pb({a[i],i}); for(auto j : qq[i]){ ans[j.sc]=get(i,j.fr,1,1,n); } } for(i=0;i<q;i++) cout<<ans[i]<<endl; } signed main(){ start(); ll t=1; //cin>>t; while(t--) solve(); return 0; } /* */

Compilation message (stderr)

jumps.cpp: In function 'void solve()':
jumps.cpp:103:10: warning: unused variable 'j' [-Wunused-variable]
  103 |     ll i,j;
      |          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...