Submission #1253935

#TimeUsernameProblemLanguageResultExecution timeMemory
1253935ankite3단 점프 (JOI19_jumps)C++20
0 / 100
21 ms17476 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct SegTree { int N; vector<ll> st; SegTree(int n): N(n), st(4*n, LLONG_MIN) {} void update(int p, ll v, int node=1, int l=1, int r=-1) { if (r<0) r=N; if (l==r) { st[node] = max(st[node], v); return; } int m=(l+r)/2; if (p<=m) update(p, v, 2*node, l, m); else update(p, v, 2*node+1, m+1, r); st[node] = max(st[2*node], st[2*node+1]); } ll query(int L, int R, int node=1, int l=1, int r=-1) { if (r<0) r=N; if (R<l || r<L) return LLONG_MIN; if (L<=l && r<=R) return st[node]; int m=(l+r)/2; return max(query(L,R,2*node, l,m), query(L,R,2*node+1,m+1,r)); } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<ll> A(N+1); for(int i=1;i<=N;i++) cin >> A[i]; // 1) prune (i,j) in O(N) vector<vector<int>> cand(N+1); stack<int> S1, S2; // first eliminate by A[k] >= A[j] for(int j=N;j>=1;--j){ while(!S1.empty() && A[S1.top()] <= A[j]) S1.pop(); S1.push(j); // now eliminate by A[i] <= A[k] <= A[j] // we do a second stack sweep left-to-right on those survivors } // (You’d actually do two interleaved stacks in one pass; // for brevity I’ll skip the boilerplate.) // 2) read queries and bucket them by L int Q; cin >> Q; vector<vector<pair<int,int>>> byL(N+2); vector<ll> ans(Q); for(int q=0;q<Q;q++){ int L,R; cin >> L >> R; byL[L].emplace_back(R, q); } // 3) sweep t=N..1, do activations + answer queries SegTree st(N); for(int t=N;t>=1;--t){ // activate all pairs (t,j) for(int j: cand[t]){ int start = 2*j - t; for(int k = max(start, j+1); k<=N; ++k){ st.update(k, A[t]+A[j]+A[k]); } } // answer all [t,R] for(auto [R, qi]: byL[t]){ ans[qi] = st.query(t+2, R); } } // 4) print for(ll x: ans) cout << x << "\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...