Submission #1264560

#TimeUsernameProblemLanguageResultExecution timeMemory
1264560nguyenphucanhkhoiTriple Jump (JOI19_jumps)C++20
27 / 100
141 ms71016 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pb push_back #define fi first #define se second #define hash vector<int> #define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++) #define REV(i, n) for (int i = (n); i >= 1; i--) #define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++) #define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--) #define MASK(k) (1 << (k)) #define BIT(i, n) (((n) >> ((i) - 1)) & 1) #define OFF(i, n) ((n) & ~MASK((i) - 1)) #define ON(i, n) ((n) | MASK((i) - 1)) #define NUM_BIT(n) (__builtin_popcount(n)) const int MAXN = 1e6 + 26; int n, m, k, x, y, a[MAXN], ans[MAXN]; pii c[MAXN]; ll lazy[4 * MAXN]; struct Node { ll mx, pr; Node(ll val = 0) { mx = pr = val; } } tree[4 * MAXN]; void build(int k, int l, int r) { if (l == r) return tree[k] = Node(a[r]), void(); int m = (l + r) >> 1; build(k << 1, l, m); build(k << 1 | 1, m + 1, r); tree[k].mx = max(tree[k << 1].mx, tree[k << 1 | 1].mx); tree[k].pr = max(tree[k << 1].pr, tree[k << 1 | 1].pr); } void fix(int k, int l, int r) { if (!lazy[k]) return; tree[k].mx = max(tree[k].mx, tree[k].pr + lazy[k]); if (l != r) { lazy[k << 1] = max(lazy[k << 1], lazy[k]); lazy[k << 1 | 1] = max(lazy[k << 1 | 1], lazy[k]); } lazy[k] = 0; } void update(int k, int l, int r, int u, int v, ll f) { fix(k, l, r); if (l > v || r < u) return; if (l >= u && r <= v) { lazy[k] = f; fix(k, l, r); return; } int m = (l + r) >> 1; update(k << 1, l, m, u, v, f); update(k << 1 | 1, m + 1, r, u, v, f); tree[k].mx = max(tree[k << 1].mx, tree[k << 1 | 1].mx); } ll get(int k, int l, int r, int u, int v) { fix(k, l, r); if (l > v || r < u) return -1e18; if (l >= u && r <= v) return tree[k].mx; int m = (l + r) >> 1; return max(get(k << 1, l, m, u, v), get(k << 1 | 1, m + 1, r, u, v)); } struct query { int l, r, id; } b[MAXN]; void find_pairs() { stack<int> st; REP(i, n) { while (!st.empty() && a[st.top()] <= a[i]) { c[++k] = {st.top(), i}; st.pop(); } if (!st.empty()) c[++k] = {st.top(), i};; st.push(i); } sort(c + 1, c + k + 1, greater<pii>()); } bool cmp(query i1, query i2) { return i1.l < i2.l; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; REP(i, n) cin >> a[i]; cin >> m; REP(i, m) cin >> x >> y, b[i] = {x, y, i}; find_pairs(); build(1, 1, n); sort(b + 1, b + m + 1, cmp); int j = 1; REP(i, m) { int l = b[i].l, r = b[i].r; while (c[j].fi >= l && j <= k) { int x = c[j].fi, y = c[j].se; int p = 2 * y - x; if (p <= n) update(1, 1, n, p, n, a[x] + a[y]); j++; } int id = b[i].id; ans[id] = get(1, 1, n, l, r); } REP(i, m) cout << ans[i] << endl; 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...