Submission #674196

#TimeUsernameProblemLanguageResultExecution timeMemory
674196MohamedFaresNebiliTriple Jump (JOI19_jumps)C++14
100 / 100
1008 ms84260 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll int N, Q, A[500005], res[500005]; array<int, 3> ST[2000005]; void build(int v, int l, int r) { if(l == r) { ST[v] = {A[l], 0, A[l]}; return; } build(v * 2, l, (l + r) / 2); build(v * 2 + 1, (l + r) / 2 + 1, r); ST[v][0] = max(ST[v * 2][0], ST[v * 2 + 1][0]); ST[v][1] = max(ST[v * 2][1], ST[v * 2 + 1][1]); ST[v][2] = max({ST[v * 2][2], ST[v * 2 + 1][2], ST[v * 2][1] + ST[v * 2 + 1][0]}); } void update(int v, int l, int r, int p, int val) { if(l == r) { ST[v][1] = max(ST[v][1], val); ST[v][2] = ST[v][0] + ST[v][1]; return; } int md = (l + r) / 2; if(p <= md) update(v * 2, l, (l + r) / 2, p, val); else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val); ST[v][0] = max(ST[v * 2][0], ST[v * 2 + 1][0]); ST[v][1] = max(ST[v * 2][1], ST[v * 2 + 1][1]); ST[v][2] = max({ST[v * 2][2], ST[v * 2 + 1][2], ST[v * 2][1] + ST[v * 2 + 1][0]}); } array<int, 3> query(int v, int l, int r, int lo, int hi) { if(l > hi || r < lo) return {-1, -1, -1}; if(l >= lo && r <= hi) return ST[v]; array<int, 3> U = query(v * 2, l, (l + r) / 2, lo, hi); array<int, 3> V = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi); if(U[0] == -1) return V; if(V[0] == -1) return U; array<int, 3> ans; ans[0] = max(U[0], V[0]); ans[1] = max(U[1], V[1]); ans[2] = max({U[2], V[2], U[1] + V[0]}); return ans; } bool compare(array<int, 3> U, array<int, 3> V) { if(U[0] != V[0]) return U[0] > V[0]; return U[2] < V[2]; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; stack<int> S; for(int l = 1; l <= N; l++) cin >> A[l]; cin >> Q; build(1, 1, N); vector<array<int, 3>> E; for(int l = 1; l <= N; l++) { while(!S.empty() && A[S.top()] <= A[l]) { E.push_back({S.top(), l, -1}); S.pop(); } if(!S.empty()) E.push_back({S.top(), l, -1}); S.push(l); } for(int l = 1; l <= Q; l++) { int L, R; cin >> L >> R; E.push_back({L, R, l}); } sort(E.begin(), E.end(), compare); for(auto u : E) { if(u[2] == -1) { int k = 2 * u[1] - u[0]; if(k > N) continue; update(1, 1, N, k, A[u[0]] + A[u[1]]); } else { res[u[2]] = query(1, 1, N, u[0], u[1])[2]; } } for(int l = 1; l <= Q; l++) cout << res[l] << "\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...