Submission #1013071

#TimeUsernameProblemLanguageResultExecution timeMemory
1013071Alihan_8Triple Jump (JOI19_jumps)C++17
46 / 100
1872 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' #define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int N = 5e5 + 1; int n; struct SegTree{ vector <int> T, add; SegTree(){ T.resize(N * 8); add.resize(N * 8); } void push(int v, int l, int r){ if ( l != r ){ chmax(add[v * 2], add[v]); chmax(add[v * 2 + 1], add[v]); } chmax(T[v], add[v]); add[v] = 0; } void upd(int v, int l, int r, int tl, int tr, int x){ push(v, l, r); if ( l > tr or r < tl ){ return; } if ( tl <= l && tr >= r ){ add[v] = x; push(v, l, r); return; } int md = (l + r) >> 1; upd(v * 2, l, md, tl, tr, x); upd(v * 2 + 1, md + 1, r, tl, tr, x); T[v] = max(T[v * 2], T[v * 2 + 1]); } void upd(int l, int r, int x){ upd(1, 0, 2 * n, l, r, x); } int get(int v, int l, int r, int x){ push(v, l, r); if ( l > x ){ return 0; } if ( r <= x ){ return T[v]; } int md = (l + r) >> 1; return max(get(v * 2, l, md, x), get(v * 2 + 1, md + 1, r, x)); } int get(int x){ return get(1, 0, n * 2, x); } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; vector <int> a(n + 1); for ( int i = 1; i <= n; i++ ){ cin >> a[i]; } auto f = [&](int x, int l, int r){ int opt = 0; if ( x > l ){ // x -> b int mx = a[x - 1], j = x - 2; for ( int i = x + 1; i <= r; i++ ){ while ( j >= l && x - j <= i - x ){ chmax(mx, a[j]); j--; } chmax(opt, mx + a[i] + a[x]); } } if ( x + 2 <= r ){ // x -> a int mx = a[x + 1], j = x + 2; for ( int i = x + 2; i <= r; i++ ){ while ( j < i && i - j >= j - x ){ chmax(mx, a[j]); j++; } chmax(opt, mx + a[i] + a[x]); } } if ( x - 2 >= l ){ // x -> c multiset <int> st{a[x - 1]}; int j = x - 2; for ( int i = x - 1; i > l; i-- ){ while ( j >= l && i - j <= x - i ){ st.insert(a[j]); j--; } st.erase(st.find(a[i])); chmax(opt, *st.rbegin() + a[i] + a[x]); } } return opt; }; int q; cin >> q; if ( q == 1 ){ while ( q-- ){ int l, r; cin >> l >> r; vector <ar<int,2>> b; for ( int i = l; i <= r; i++ ){ b.pb({-a[i], i}); } sort(all(b)); vector <int> tmp; for ( int i = 0; i < min(30LL, (int)b.size()); i++ ){ tmp.pb(b[i][1]); } int opt = 0; for ( auto &i: tmp ){ chmax(opt, f(i, l, r)); } cout << opt << ln; } } else{ vector <vector<int>> dp(n + 2, vector <int> (n + 2)); for ( int i = n - 2; i > 0; i-- ){ int k = i + 1, mx = 0; for ( int j = i + 2; j <= n; j++ ){ dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); while ( k < j && k - i <= j - k ){ chmax(mx, a[k]); k++; } chmax(dp[i][j], mx + a[i] + a[j]); } } while ( q-- ){ int l, r; cin >> l >> r; cout << dp[l][r] << ln; } } cout << '\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...