/* it could have been better :) it will next time ;) */ #include <bits/stdc++.h> using namespace std; #define int long long #define INF 1e18 #define f first #define s second #define pii pair<int, int> #define vi vector<int> const int MOD = 1'000'000'000 + 7; void setIO(string name = "") { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef LOCAL freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); #else if (!name.empty()) { freopen((name + ".INP").c_str(), "r", stdin); freopen((name + ".OUT").c_str(), "w", stdout); } #endif } const int MAXN = 5e5; int n, Q; int a[MAXN + 5]; vector<pii> queries; struct Event { int type; // 0: add, 1: query int l, r; int id; Event(int l, int r): type(0), l(l), r(r) {} Event(int l, int r, int id): type(1), l(l), r(r), id(id) {} bool operator<(const Event &other) { if(l == other.l) return type < other.type; return l > other.l; } }; int ans[MAXN + 5]; struct Node { pii val; int lazy; } st[4 * MAXN + 5]; void down(int id, int l, int r) { if(st[id].lazy == 0) return; st[id].val.f = max(st[id].val.f, st[id].val.s + st[id].lazy); if(l != r) { st[id * 2].lazy = max(st[id * 2].lazy, st[id].lazy); st[id * 2 + 1].lazy = max(st[id * 2 + 1].lazy, st[id].lazy); } st[id].lazy = 0; } void build(int id, int l, int r) { if(l == r) { st[id].val = {0, a[l]}; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); st[id].val.s = max(st[id * 2].val.s, st[id * 2 + 1].val.s); } int query(int id, int l, int r, int u, int v) { down(id, l, r); if(v < l || r < u) return -INF; if(u <= l && r <= v) return st[id].val.f; int mid = (l + r) / 2; return max(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v)); } void upd(int id, int l, int r, int u, int v, int k) { down(id, l, r); if(v < l || r < u) return; if(u <= l && r <= v) { st[id].lazy = max(st[id].lazy, k); down(id, l, r); return; } int mid = (l + r) / 2; upd(id * 2, l, mid, u, v, k); upd(id * 2 + 1, mid + 1, r, u, v, k); st[id].val.f = max(st[id * 2].val.f, st[id * 2 + 1].val.f); st[id].val.s = max(st[id * 2].val.s, st[id * 2 + 1].val.s); } void solve() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; cin >> Q; vector<Event> events; for(int i = 1; i <= Q; i++) { int l, r; cin >> l >> r; events.push_back({l, r, i}); } { vi stk; for(int i = n; i >= 1; i--) { while(!stk.empty() && a[i] > a[stk.back()]) { events.push_back(Event(i, stk.back())); stk.pop_back(); } if(!stk.empty()) { events.push_back(Event(i, stk.back())); // cout << i << ' ' << x << '\n'; } stk.push_back(i); } } build(1, 1, n); sort(events.begin(), events.end()); for(auto e : events) { // cout << e.type << ' ' << e.l << ' ' << e.r << '\n'; if(e.type == 0) { if(2 * e.r - e.l <= n) { upd(1, 1, n, 2 * e.r - e.l, n, a[e.l] + a[e.r]); } } else { ans[e.id] = query(1, 1, n, e.l, e.r); } } for(int i = 1; i <= Q; i++) cout << ans[i] << '\n'; } signed main() { setIO(); int t = 1; // cin >> t; while (t--) solve(); }

jumps.cpp: In function 'void setIO(std::string)':
jumps.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~