제출 #943545

#제출 시각아이디문제언어결과실행 시간메모리
943545PlayVoltz3단 점프 (JOI19_jumps)C++17
0 / 100
164 ms53160 KiB
#include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second vector<int> vect; struct node { node *left, *right; int S, E, val, r_val, A_val, pv; node(int _s, int _e) : S(_s), E(_e), r_val(-(int)1e9), pv(-(int)1e9) { if (S == E) { A_val = vect[S]; return; } int M = (S + E) / 2; left = new node(S, M); right = new node(M + 1, E); A_val = max(left->A_val, right->A_val); } void prop() { left->r_val = max(left->r_val, pv + left->A_val); left->pv = max(left->pv, pv); right->r_val = max(right->r_val, pv + right->A_val); right->pv = max(right->pv, pv); } void up(int l, int r, int v) { if (l > E || r < S) { return; } if (l <= S && E <= r) { r_val = max(r_val, v + A_val); pv = max(pv, v); return; } prop(); left->up(l, r, v); right->up(l, r, v); r_val = max(left->r_val, right->r_val); } int query(int l, int r) { if (l > E || r < S) { return -(int)1e9; } if (l <= S && E <= r) { return r_val; } prop(); return max(left->query(l, r), right->query(l, r)); } } *st; int32_t main(){ int n, q, a, b; cin>>n; vect.resize(n+1); vector<vector<pii> > queries(n+1); for (int i=1; i<=n; ++i)cin>>vect[i]; cin>>q; vector<int> ans(q); vector<vector<int> > next(n+1); st = new node(1, n); for (int i=0; i<q; ++i){ cin>>a>>b; queries[a].pb(mp(b, i)); } stack<int> s; for (int i=1; i<=n; ++i){ while (!s.empty()&&vect[s.top()]<vect[i])next[s.top()].pb(i), s.pop(); s.push(i); } while (!s.empty())s.pop(); for (int i=n; i>=1; --i){ while (!s.empty()&&vect[s.top()]<vect[i])next[i].pb(s.top()), s.pop(); s.push(i); } for (int i=n; i>=1; --i){ for (auto c:next[i])st->up(2*c-i, n, vect[i]+vect[c]); for (auto c:queries[i])ans[c.se]=st->query(i, c.fi); } for (auto a:ans)cout<<a<<"\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...