Submission #746507

#TimeUsernameProblemLanguageResultExecution timeMemory
746507GrindMachineTriple Jump (JOI19_jumps)C++17
100 / 100
690 ms121636 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: https://codeforces.com/blog/entry/68269?#comment-527139 edi choose l <= a < b < c <= r s.t: b-a <= c-b arr[a]+arr[b]+arr[c] is max let's say we fix (a,b) when can we consider (a,b) as an option if there is a guy in between with a higher val, then we dont have to consider pair (a,b) if there exists k s.t a < k < b with arr[k] >= arr[a] or arr[k] >= arr[b], then we can do this: arr[k] >= arr[a]: set a = k arr[k] >= arr[b]: set b = k by doing this, we reduce the jump distance from a to b so we have more options for c in short, consider pair (a,b) only if there is nobody in between with a higher or equal value how many such pairs are there? iterate over b from 1 to n and find all valid a maintain all valid a values when increasing b once some a becomes bad (some >= guy appears in between), he never becomes good for bigger b we want to find all a for whom nobody >= them has appeared in [a,b] so far when moving to a new b, we can make pairs (a,b) for all active a then we will remove all a values for which arr[a] <= arr[b] (yet to complete explanation) */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; template<typename T> struct segtree { // https://codeforces.com/blog/entry/18051 /*=======================================================*/ struct data { ll mx1, mx2, res; }; data neutral = {-inf2, -inf2, -inf2}; data merge(data &left, data &right) { data curr; curr.mx1 = max(left.mx1,right.mx1); curr.mx2 = max(left.mx2,right.mx2); curr.res = max({left.res, right.res, left.mx2 + right.mx1}); return curr; } void create(int i, T v) { tr[i].mx1 = v; } void modify(int i, T v) { amax(tr[i].mx2, v); tr[i].res = tr[i].mx1 + tr[i].mx2; } /*=======================================================*/ int n; vector<data> tr; segtree() { } segtree(int siz) { init(siz); } void init(int siz) { n = siz; tr.assign(2 * n, neutral); } void build(vector<T> &a, int siz) { rep(i, siz) create(i + n, a[i]); rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } void pupd(int i, T v) { modify(i + n, v); for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } data query(int l, int r) { data resl = neutral, resr = neutral; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) resl = merge(resl, tr[l++]); if (!(r & 1)) resr = merge(tr[r--], resr); } return merge(resl, resr); } }; void solve(int test_case) { ll n; cin >> n; vector<ll> arr(n+5); rep1(i,n) cin >> arr[i]; vector<ll> good; vector<pll> pairs; rep1(b,n){ while(!good.empty() and arr[b] >= arr[good.back()]){ pairs.pb({good.back(), b}); good.pop_back(); } if(!good.empty()){ pairs.pb({good.back(), b}); } good.pb(b); } // for(auto [a, b] : pairs){ // if(a < 3) conts; // ll dis = b - a; // ll min_c = b + dis; // ll val = 0; // for(int c = min_c; c <= 12; ++c){ // amax(val, arr[a]+arr[b]+arr[c]); // } // pll px = {a, b}; // debug(px); // debug(val); // cout << endl; // } vector<ll> enter[n+5]; for(auto [a,b] : pairs){ enter[a].pb(b); } ll q; cin >> q; vector<pll> queries[n+5]; rep1(i,q){ ll l,r; cin >> l >> r; queries[l].pb({r, i}); } vector<ll> ans(q+5); segtree<ll> st(n+5); st.build(arr,n+1); rev(l,n,1){ trav(b,enter[l]){ ll dis = b - l; ll c = b + dis; if(c <= n){ st.pupd(c, arr[l] + arr[b]); } } for(auto [r, id] : queries[l]){ ans[id] = st.query(l,r).res; } } rep1(i,q) cout << ans[i] << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...