Submission #1241212

#TimeUsernameProblemLanguageResultExecution timeMemory
1241212trantrungkeinTriple Jump (JOI19_jumps)C++20
27 / 100
146 ms45496 KiB
#include<bits/stdc++.h> #define int long long using namespace std; #define For(i,a,b) for(int i = (a); i <= (b); ++i) const int N = 5e5 + 1; vector<int> g[N]; struct Node { int r,id; }; vector<Node> quer[N]; pair<int,int> st[4*N];int lazy[4*N],ans[N],a[N],n; void Push(int id, int l, int r) { if(!lazy[id]) return; st[id].first = max(st[id].first,st[id].second+lazy[id]); if(l != r) { lazy[2*id] = lazy[2*id+1] = lazy[id]; } lazy[id] = 0; } pair<int,int> Merge(pair<int,int> a, pair<int,int> b) { return {max(a.first,b.first),max(a.second,b.second)}; } void build(int id, int l, int r) { if(l > r) return; if(l == r) { st[id] = {a[l],a[l]}; return; } int mid = (l+r)/2; build(2*id,l,mid); build(2*id+1,mid+1,r); st[id] = Merge(st[2*id],st[2*id+1]); } void update(int id, int l, int r, int u, int v, int val) { Push(id,l,r); if(l > v || r < u) return; if(u <= l && r <= v) { lazy[id] = val; Push(id,l,r); return; } int mid = (l+r)/2; update(2*id,l,mid,u,v,val); update(2*id+1,mid+1,r,u,v,val); st[id] = Merge(st[2*id],st[2*id+1]); } int get(int id, int l, int r, int u, int v) { Push(id,l,r); if(l > v || r < u) return 0; if(u <= l && r <= v) {return st[id].first;} int mid = (l+r)/2; Push(id,l,r); return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v)); } int32_t main() { //freopen("kien.inp","r",stdin); // freopen("kien.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n; vector<int> st; For(i,1,n) { cin >> a[i]; while(!st.empty() && a[i] >= a[st.back()]) { g[st.back()].push_back(i); st.pop_back(); } if(!st.empty()) g[st.back()].push_back(i); st.push_back(i); } build(1,1,n); int q; cin >> q; For(i,1,q) { int l,r; cin >> l >> r; quer[l].push_back({r,i}); } for(int i = n-2; i >= 1; i--) { for(int id : g[i]) update(1,1,n,2*id-i,n,a[i]+a[id]); for(auto [r,id] : quer[i]) { ans[id] = get(1,1,n,i,r); } } For(i,1,q) cout << ans[i] <<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...