Submission #570631

#TimeUsernameProblemLanguageResultExecution timeMemory
570631MohammadAghilTriple Jump (JOI19_jumps)C++14
100 / 100
1056 ms77272 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<long double, ll> pp; #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353, maxn = 5e5 + 5, lg = 19, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} ll a[maxn]; int n, q; void slv2(){ vector<vector<ll>> mx(n, vector<ll>(n, -inf)); rep(i,0,n){ mx[i][i] = a[i]; rep(j,i+1,n) mx[i][j] = max(mx[i][j-1], a[j]); } vector<vector<ll>> ans(n, vector<ll>(n, -inf)); rep(l,3,n+1){ rep(i,0,n-l+1){ int j = i + l - 1; ans[i][j] = max({ans[i+1][j], ans[i][j-1], a[i] + a[j] + mx[i+1][(i+j)>>1]}); } } while(q--){ int l, r; cin >> l >> r; cout << ans[--l][--r] << '\n'; } } template<class T> struct Rmq{ vector<vector<T>> rmq; vector<int> lgg; T comb(T a, T b){ return max(a, b); } Rmq(vector<T> a){ int n = sz(a); lgg.resize(n + 1); rep(i,2,n + 1) lgg[i] = lgg[i>>1] + 1; rmq.assign(lgg[n] + 1, vector<T>(n)); rmq[0] = a; rep(i,1,lgg[n] + 1){ rep(j,0,n-(1<<i)+1){ rmq[i][j] = comb(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]); } } } T get(int l, int r){ // 0-base [l, r] int g = lgg[r - l + 1]; return comb(rmq[g][l], rmq[g][r - (1<<g) + 1]); } }; void slv3(){ int l, r; cin >> l >> r; l--, r--, n = r - l + 1; vector<int> b(a + l, a + r + 1); Rmq<int> rmq(b); auto get_max = [&](int l, int r){ if(l > r || r < 0) return -1; l = max(0, l), r = min(r, n-1); return rmq.get(l, r); }; auto clc = [&](int i){ ll res = -inf; // right rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(j-(i-j),j-1)); // center rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(i+(i-j),n-1)); // left rep(j,i+1,n) res = max(res, 1ll*b[i] + b[j] + get_max(j+(j-i),n-1)); return res; }; vector<int> c(n); iota(all(c), 0), sort(all(c), [&](int i, int j){ return b[i] > b[j]; }); ll ans = 0; int g = min(int(log2(n))+3, n); rep(i,0,g){ ans = max(ans, clc(c[i])); } cout << ans << '\n'; } ll seg[maxn<<2]; int laz[maxn<<2]; int vl[maxn<<2]; void updNode(int x, int k){ seg[x] = max(seg[x], 1ll*vl[x] + k), laz[x] = max(laz[x], k); } void shift(int x){ if(laz[x]){ updNode(x<<1, laz[x]); updNode(x<<1|1, laz[x]); laz[x] = 0; } } void build(int x = 1, int lx = 0, int rx = n){ if(lx + 1 == rx) { vl[x] = seg[x] = a[lx]; return; } int mid = (lx + rx)>>1; build(x<<1, lx, mid), build(x<<1|1, mid, rx); seg[x] = vl[x] = max(vl[x<<1], vl[x<<1|1]); } void upd(int l, int r, int k, int x = 1, int lx = 0, int rx = n){ if(l <= lx && r >= rx){ updNode(x, k); return; } if(l >= rx || r <= lx) return; int mid = (lx + rx)>>1; shift(x); upd(l, r, k, x<<1, lx, mid), upd(l, r, k, x<<1|1, mid, rx); seg[x] = max(seg[x<<1], seg[x<<1|1]); } ll get(int l, int r, int x = 1, int lx = 0, int rx = n){ if(l <= lx && r >= rx) return seg[x]; if(l >= rx || r <= lx) return -1; int mid = (lx + rx)>>1; shift(x); return max(get(l, r, x<<1, lx, mid), get(l, r, x<<1|1, mid, rx)); } void slv4(){ build(); vector<vector<pp>> st(n); vector<ll> ans(q); rep(i,0,q){ int l, r; cin >> l >> r; l--, r--; st[l].pb({r, i}); } vector<int> stk; per(i,n-1,0){ vector<int> candj; while(sz(stk) && a[stk.back()] < a[i]) candj.pb(stk.back()), stk.pop_back(); if(sz(stk)) candj.pb(stk.back()); stk.pb(i); for(int j: candj){ int k = j+j-i; if(k > n) continue; upd(k, n, a[i] + a[j]); } for(auto[r,id]: st[i]) ans[id] = get(i, r+1); } for(ll c: ans) cout << c << '\n'; } int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n; rep(i,0,n) cin >> a[i]; cin >> q; slv4(); return 0; }

Compilation message (stderr)

jumps.cpp: In function 'void slv4()':
jumps.cpp:161:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  161 |           for(auto[r,id]: st[i]) ans[id] = get(i, r+1);
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...