제출 #1097227

#제출 시각아이디문제언어결과실행 시간메모리
1097227coldbr3w3단 점프 (JOI19_jumps)C++17
100 / 100
1110 ms145752 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 5e5 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 350; ll n,q; ll a[N], nxt[N], res[N]; vector<ll>candi[N]; vector<pll>t[N]; struct segment_tree{ ll n; vector<ll>st, lz, mx, val; void init(ll _n){ n = _n; st.clear(); st.resize(4 * n + 10, 0); lz.clear(); lz.resize(4 * n + 10, 0); mx.clear(); mx.resize(4 * n + 10); val.clear(); val.resize(4 * n + 10); build(1,1,n); } void build(ll id, ll l, ll r){ st[id] = -inf; val[id] = -inf; if(l == r){ mx[id] = a[l]; return; } ll mid = (l + r) / 2; build(2 * id, l, mid); build(2 * id + 1, mid + 1, r); mx[id] = max(mx[2 * id], mx[2 * id + 1]); } void down(ll id, ll l, ll r){ st[id] = max(lz[id], st[id]); val[id] = max(val[id], mx[id] + st[id]); if(l != r) lz[2 * id] = max(lz[2 * id], lz[id]), lz[2 * id + 1] = max(lz[2 * id + 1], lz[id]); lz[id] = 0; } void update(ll id, ll l, ll r, ll left, ll right, ll v){ down(id, l, r); if(l > right || r < left) return; if(left <= l && r <= right){ lz[id] = max(lz[id], v); down(id, l, r); return; } ll mid = (l + r) / 2; update(2 * id, l, mid, left, right, v); update(2 * id + 1, mid + 1, r, left, right, v); val[id] = max(val[2 * id], val[2 * id + 1]); } ll get(ll id, ll l, ll r, ll left, ll right){ down(id, l, r); if(l > right || r < left) return -inf; if(left <= l && r <= right) return val[id]; ll mid = (l + r) / 2; return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right)); } void update(ll l, ll r, ll val){update(1,1,n,l,r,val);} ll get(ll l, ll r){return get(1,1,n,l,r);} } st; void to_thic_cau(){ cin >> n; for(int i = 1; i <= n;i++) cin >> a[i]; a[n+1] = a[0] = inf; stack<ll>s; s.push(n + 1); for(int i = n; i >= 1;i--){ while(a[s.top()] < a[i]) s.pop(); if(s.top() <= n) candi[i].pb(s.top()); s.push(i); } while(s.size()) s.pop(); s.push(0); for(int i = 1; i <= n;i++){ while(a[s.top()] < a[i]) s.pop(); if(s.top() >= 1) candi[s.top()].pb(i); s.push(i); } cin >> q; for(int i = 1; i <= q;i++){ ll l,r; cin >> l >> r; t[l].pb({r, i}); } st.init(n); for(int i = n; i >= 1;i--){ for(auto x : candi[i]){ ll len = x - i; if(x + len <= n) st.update(x + len, n, a[i] + a[x]); } for(auto x : t[i]) res[x.S] = st.get(i, x.F); } for(int i = 1; i <= q;i++) cout << res[i] << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...