Submission #1255917

#TimeUsernameProblemLanguageResultExecution timeMemory
1255917mngoc._.3단 점프 (JOI19_jumps)C++20
100 / 100
842 ms65732 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int , int> const int N = 5e5 + 5; pii st[4 * N]; int stadd[4 * N]; int a[N]; int res[N]; vector<pii> queries[N]; int n , q; bool cmp(const pii& x, const pii& y){ return x.second < y.second; } void build(int idx , int l , int r){ if(l == r){ st[idx].first = a[l]; st[idx].second = a[l]; return; } int mid = (l + r) / 2; build(2 * idx , l , mid); build(2 * idx + 1 , mid + 1 , r); st[idx].first = max(st[2 * idx].first , st[2 * idx + 1].first); st[idx].second = st[idx].first; } void update(int idx , int l , int r , int u , int v , int val){ if(l > v || r < u) return; if(u <= l && r <= v){ stadd[idx] = max(stadd[idx] , val); st[idx].second = max(st[idx].second , st[idx].first + val); return; } int mid = (l + r) / 2; update(2 * idx , l , mid , u , v, val); update(2 * idx + 1 , mid + 1 , r , u , v , val); st[idx].second = max({st[2 * idx].second , st[2 * idx + 1].second , st[idx].first + stadd[idx]}); } pii get(int idx , int l , int r , int u , int v){ if(l > v || r < u) return {0 , 0}; if(u <= l && r <= v) return st[idx]; int mid = (l + r) / 2; pii t1 = get(2 * idx , l , mid , u , v); pii t2 = get(2 * idx + 1 , mid + 1 , r , u , v); return make_pair(max(t1.first , t2.first) , max({t1.second , t2.second , max(t1.first, t2.first) + stadd[idx]})); } void upd(int l , int r){ int pos = r * 2 - l; if(pos > n) return; update(1 , 1 , n , pos , n , a[l] + a[r]); } void emconhoanhko(void){ stack<int> s; for(int i = n ; i >= 1 ; i--){ while(s.size() && a[i] >= a[s.top()]){ upd(i , s.top()); s.pop(); } if(s.size()) upd(i , s.top()); s.push(i); for(auto x : queries[i]) res[x.second] = get(1 , 1 , n , i , x.first).second; } } void solve(void){ cin >> n; for(int i = 1 ; i <= n ; i++) cin >> a[i]; cin >> q; for(int i = 1 ; i <= q; i++){ int l , r; cin >> l >> r; queries[l].push_back({r , i}); } build(1 , 1 , n); emconhoanhko(); for(int i = 1 ; i <= q ; i++) cout << res[i] << endl; } signed main(void){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); 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...