Submission #908683

#TimeUsernameProblemLanguageResultExecution timeMemory
908683Shayan86Triple Jump (JOI19_jumps)C++14
100 / 100
885 ms80060 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define Mp make_pair #define sep ' ' #define endl '\n' #define F first #define S second #define pb push_back #define all(x) (x).begin(),(x).end() #define kill(res) cout << res << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout); #define lid (id*2) #define rid (id*2+1) #define mid ((l+r)/2) const ll N = 5e5 + 50; const ll Mod = 1e18; ll n, q, arr[N], res[N]; vector<int> sta; vector<pii> qu[N]; pll seg[N*4]; ll lz[N*4]; pll merg(pll l, pll r){ return {max(l.F, r.F), max(l.S, r.S)}; } void build(int l = 1, int r = n+1, int id = 1){ if(l+1 == r){ seg[id].F = seg[id].S = arr[l]; return; } build(l, mid, lid); build(mid, r, rid); seg[id] = merg(seg[lid], seg[rid]); } void quex(int id, ll x){ seg[id].F = max(seg[id].F, seg[id].S + x); lz[id] = max(lz[id], x); } void relax(int id){ quex(lid, lz[id]); quex(rid, lz[id]); } void upd(int ql, int qr, ll x, int l = 1, int r = n+1, int id = 1){ if(qr <= l || r <= ql) return; if(ql <= l && r <= qr){ quex(id, x); return; } relax(id); upd(ql, qr, x, l, mid, lid); upd(ql, qr, x, mid, r, rid); seg[id] = merg(seg[lid], seg[rid]); } pll get(int ql, int qr, int l = 1, int r = n+1, int id = 1){ if(qr <= l || r <= ql) return {0, 0}; if(ql <= l && r <= qr) return seg[id]; relax(id); return max(get(ql, qr, l, mid, lid), get(ql, qr, mid, r, rid)); } int main(){ fast_io; cin >> n; for(int i = 1; i <= n; i++) cin >> arr[i]; cin >> q; for(int i = 1; i <= q; i++){ int l, r; cin >> l >> r; qu[l].pb({r, i}); } build(); sta.pb(n); for(int i = n-1; i >= 1; i--){ while(!sta.empty()){ int lst = sta.back(); sta.pop_back(); upd(lst + lst - i, n+1, arr[i] + arr[lst]); if(arr[lst] >= arr[i]){ sta.pb(lst); break; } } sta.pb(i); for(auto [j, id]: qu[i]) res[id] = get(i, j+1).F; } for(int i = 1; i <= q; i++) cout << res[i] << endl; }

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:109:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         for(auto [j, id]: qu[i]) res[id] = get(i, j+1).F;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...