Submission #1226573

#TimeUsernameProblemLanguageResultExecution timeMemory
1226573trinhvtuanTriple Jump (JOI19_jumps)C++17
5 / 100
4094 ms5956 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 500005; int A[MAXN]; int seg[4 * MAXN]; // Segment tree for range max // Build segment tree void build(int id, int l, int r) { if (l == r) { seg[id] = A[l]; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); seg[id] = max(seg[id * 2], seg[id * 2 + 1]); } // Query segment tree for max in range [u, v] int getMax(int id, int l, int r, int u, int v) { if (r < u || l > v) return -1e18; if (u <= l && r <= v) return seg[id]; int mid = (l + r) / 2; return max(getMax(id * 2, l, mid, u, v), getMax(id * 2 + 1, mid + 1, r, u, v)); } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; for (int i = 1; i <= N; ++i) cin >> A[i]; build(1, 1, N); // Build the segment tree int Q; cin >> Q; while (Q--) { int L, R; cin >> L >> R; int res = -1e18; for (int b = L + 1; b <= R - 1; ++b) { for (int a = L; a < b; ++a) { int minC = 2 * b - a; if (minC > R) continue; int maxC = R; int maxVal = getMax(1, 1, N, minC, maxC); res = max(res, A[a] + A[b] + maxVal); } } cout << res << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...