Submission #1145480

#TimeUsernameProblemLanguageResultExecution timeMemory
1145480VMaksimoski008Triple Jump (JOI19_jumps)C++20
0 / 100
341 ms112144 KiB
#include <bits/stdc++.h> #define ar array //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const ll inf = 1e18; const int maxn = 1e5 + 5; struct segment_tree { struct node { ll pref, suf, ans; node(ll a=-5e9, ll b=-5e9) { pref = a; suf = b; ans = a + b; } }; node merge(node a, node b) { node res; res.pref = max(a.pref, b.pref); res.suf = max(a.suf, b.suf); res.ans = max({ a.ans, b.ans, a.pref + b.suf }); return res; } int n; vector<node> tree; segment_tree(int _n): n(_n), tree(4*n) {} void update(int u, int tl, int tr, int p, int t, int v) { if(tl == tr) { if(!t) tree[u].pref = v; else tree[u].suf = v; tree[u].ans = tree[u].pref + tree[u].suf; } else { int tm = (tl + tr) / 2; if(p <= tm) update(2*u, tl, tm, p, t, v); else update(2*u+1, tm+1, tr, p, t, v); tree[u] = merge(tree[2*u], tree[2*u+1]); } } node query(int u, int tl, int tr, int l, int r) { if(tl > r || l > tr) return node(); if(l <= tl && tr <= r) return tree[u]; int tm = (tl + tr) / 2; return merge(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r)); } void update(int p, int t, int v) { update(1, 1, n, p, t, v); } node query(int l, int r) { return query(1, 1, n, l, r); } }; signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n, q; cin >> n; vector<int> a(n+1); for(int i=1; i<=n; i++) cin >> a[i]; vector<pii> imp; stack<int> st; for(int i=n; i>=1; i--) { while(!st.empty() && a[st.top()] < a[i]) st.pop(); if(!st.empty()) imp.push_back({ i, st.top() }); st.push(i); } while(!st.empty()) st.pop(); for(int i=n; i>=1; i--) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); if(!st.empty()) imp.push_back({ i, st.top() }); st.push(i); } while(!st.empty()) st.pop(); for(int i=1; i<=n; i++) { while(!st.empty() && a[st.top()] < a[i]) st.pop(); if(!st.empty()) imp.push_back({ st.top(), i }); st.push(i); } while(!st.empty()) st.pop(); for(int i=1; i<=n; i++) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); if(!st.empty()) imp.push_back({ st.top(), i }); st.push(i); } cin >> q; vector<ar<int, 2> > qus[n+1]; for(int i=1; i<=q; i++) { int l, r; cin >> l >> r; qus[r].push_back({ l, i }); } vector<ar<int, 3> > vec; for(auto [x, y] : imp) vec.push_back({ x, y, 0 }); sort(vec.begin(), vec.end(), [&](ar<int, 3> x, ar<int, 3> y) { return 2 * x[1] - x[0] < 2 * y[1] - y[0]; }); for(int i=0; i<vec.size(); i++) vec[i][2] = i + 1; vector<ar<int, 3> > ord = vec; sort(vec.begin(), vec.end(), [&](ar<int, 3> x, ar<int, 3> y) { return x[1] < y[1]; }); vector<ll> ans(q+1); int m = vec.size(), j = 0, k = 0; segment_tree sgt(m); for(int i=1; i<=n; i++) { while(j < m && vec[j][1] <= i) { sgt.update(vec[j][2], 0, a[vec[j][0]] + a[vec[j][1]]); j++; } while(k < m && 2 * vec[k][1] - vec[k][0] <= i) { sgt.update(k+1, 1, a[i]); k++; } for(auto [j, id] : qus[i]) ans[id] = sgt.query(j, i).ans; } for(int i=1; i<=q; i++) 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...