Submission #970348

#TimeUsernameProblemLanguageResultExecution timeMemory
970348efedmrlrTriple Jump (JOI19_jumps)C++17
100 / 100
436 ms94684 KiB
#include <bits/stdc++.h> #define int long long int #define pb push_back #define MP make_pair #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define REP(i, n) for(int i = 0; (i) < (n); (i)++) #define ld long double using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 1e5 + 5; const int INF = 1e9 + 500; struct Node { int ar, f, mx; Node() : ar(0), f(0), mx(0) {} Node comb(Node &oth) { Node ret; ret.ar = max(ar, oth.ar); ret.f = max(f, oth.f); ret.mx = max(mx, oth.mx); ret.mx = max(ret.mx, f + oth.ar); return ret; } }; struct SegT { vector<Node> st; int n; void reset(int nn) { n = nn; st.assign(2*(n + 3), Node()); } void build() { for(int i = n - 1; i>0; i--) { st[i] = st[i << 1].comb(st[(i << 1) | 1]); } } void update(int ind, int val) { ind += n; st[ind].f = max(st[ind].f, val); st[ind].mx = max(st[ind].mx, st[ind].f + st[ind].ar); for(; ind > 1; ind >>= 1) { if(ind & 1) ind ^= 1; st[ind >> 1] = st[ind].comb(st[ind | 1]); } } int query(int l, int r) { Node lret, rret; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) lret = lret.comb(st[l++]); if(r & 1) rret = st[--r].comb(rret); } return lret.comb(rret).mx; } int queryc(int l, int r) { return query(l, r + 1); } }; int n, q; vector<int> a; vector<array<int, 3> > qu; vector<vector<int> > pr; void solve() { cin >> n; a.resize(n + 1); for(int i = 1; i<=n; i++) { cin >> a[i]; } cin >> q; qu.resize(q); REP(i, q) { cin >> qu[i][0] >> qu[i][1]; qu[i][2] = i; } vector<array<int, 2> > stck; pr.assign(n + 1, vector<int>()); for(int i = 1; i<=n; i++) { while(stck.size() && stck.back()[0] <= a[i]) { pr[stck.back()[1]].pb(i); stck.pop_back(); } if(stck.size()) { pr[stck.back()[1]].pb(i); } stck.pb({a[i], i}); } SegT st; st.reset(n + 1); for(int i = 1; i <= n; i++) { st.st[i + st.n].ar = a[i]; } st.build(); sort(rall(qu)); vector<int> res(q + 1); // for(int i = 1; i <= n; i++) { // for(int j : pr[i]) { // cout << i << " " << j << "\n"; // } // } int cur = n; for(auto &c : qu) { while(cur > c[0]) { cur--; for(auto x : pr[cur]) { if(2 * x - cur > n) continue; st.update(2 * x - cur, a[x] + a[cur]); } } res[c[2]] = st.queryc(c[0], c[1]); } for(int i = 0; i < q; i++) { cout << res[i] << "\n"; } } signed main() { fastio(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...