Submission #242392

#TimeUsernameProblemLanguageResultExecution timeMemory
242392tqbfjotldTriple Jump (JOI19_jumps)C++14
100 / 100
1168 ms99416 KiB
#include <bits/stdc++.h> using namespace std; int n; long long arr[500005]; vector<pair<int,int> > abpairs; long long ans[500005]; vector<pair<pair<int,int>,int> > queries; struct node{ int s,e; long long ab,c,abc; node *l,*r; node(int _s, int _e){ s = _s; e = _e; if (s==e){ c = arr[s]; ab = -999999999999LL; abc = -999999999999LL; } else{ l = new node(s,(s+e)/2); r = new node((s+e)/2+1,e); mergeval(); } } void mergeval(){ if (s==e){ abc = ab+c; } else{ ab = max(l->ab,r->ab); c = max(l->c,r->c); abc = max(max(l->abc,r->abc),l->ab+r->c); } } void upd(int pos, long long val){ if (s==e){ ab = max(ab,val); } else if (pos>(s+e)/2){ r->upd(pos,val); } else{ l->upd(pos,val); } mergeval(); } pair<long long,pair<long long,long long> > query(int a, int b){ if (a<=s && e<=b){ return {abc,{ab,c}}; } if (b<=(s+e)/2){ return l->query(a,b); } if (a>(s+e)/2){ return r->query(a,b); } auto lv = l->query(a,b); auto rv = r->query(a,b); return {max(max(lv.first,rv.first),lv.second.first+rv.second.second),{max(lv.second.first,rv.second.first),max(lv.second.second,rv.second.second)}}; } }*root; int main(){ scanf("%d",&n); for (int x = 0; x<n; x++){ scanf("%lld",&arr[x]); } root = new node(0,n+3); stack<long long> st; for (int x = 0; x<n; x++){ if (st.empty()){ st.push(x); continue; } while ((!st.empty()) && arr[x]>=arr[st.top()]){ abpairs.push_back({st.top(),x}); st.pop(); } if (!st.empty()){ abpairs.push_back({st.top(),x}); } st.push(x); } sort(abpairs.begin(),abpairs.end()); int q; scanf("%d",&q); for (int x = 0; x<q; x++){ int a,b; scanf("%d%d",&a,&b); a--;b--; queries.push_back({{a,b},x}); } sort(queries.begin(),queries.end()); int c = abpairs.size()-1; for (int x = q-1; x>=0; x--){ while (c>=0 && abpairs[c].first>=queries[x].first.first){ int pos = abpairs[c].second*2-abpairs[c].first; root->upd(min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]); //printf("upd %d, %d\n",min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]); c--; } ans[queries[x].second] = root->query(queries[x].first.first,queries[x].first.second).first; } for (int x = 0; x<q; x++){ printf("%lld\n",ans[x]); } }

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...