Submission #1190770

#TimeUsernameProblemLanguageResultExecution timeMemory
1190770son2008Triple Jump (JOI19_jumps)C++20
100 / 100
683 ms66708 KiB
#include<bits/stdc++.h> using namespace std; #define task "task" #define ii pair<int,int> #define fi first #define se second #define int long long #define ll long long #define ld double #define mp make_pair #define lg2 30 #define iii pair<int,ii> #define iiii pair<ii,ii> #define base 29 #define eps 1e-8 int dx[]= {0LL,0LL,1,-1,1,1,-1,-1}; int dy[]= {1,-1,0LL,0LL,1,-1,1,-1}; const int maxn=5e5+1; const int mod=1e9+7; int n,a[maxn],mx[4*maxn],tree[4*maxn],lazy[4*maxn],ans[maxn],q; vector<ii>query[maxn]; void build(int id,int l,int r) { if(l==r) { tree[id]=mx[id]=a[l]; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); tree[id]=max(tree[id*2],tree[id*2+1]); mx[id]=max(mx[id*2],mx[id*2+1]); } void down(int id) { int &w=lazy[id]; tree[id*2]=max(tree[id*2],mx[id*2]+w); tree[id*2+1]=max(tree[id*2+1],mx[id*2+1]+w); lazy[id*2]=max(lazy[id*2],w); lazy[id*2+1]=max(lazy[id*2+1],w); w=0; } void update(int id,int l,int r,int u,int v,int w) { if(u>r||v<l)return; if(u<=l&&v>=r) { tree[id]=max(tree[id],mx[id]+w); lazy[id]=max(lazy[id],w); return; } int mid=(l+r)/2; down(id); update(id*2,l,mid,u,v,w); update(id*2+1,mid+1,r,u,v,w); tree[id]=max(tree[id*2],tree[id*2+1]); } int get(int id,int l,int r,int u,int v) { if(u>r||v<l)return 0; if(u<=l&&v>=r)return tree[id]; down(id); int mid=(l+r)/2; return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v)); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } 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; query[l].push_back({r,i}); } build(1,1,n); stack<int>s; for(int i=n;i>=1;i--) { while(!s.empty()&&a[i]>=a[s.top()]) { update(1,1,n,2*s.top()-i,n,a[i]+a[s.top()]); s.pop(); } if(s.size())update(1,1,n,2*s.top()-i,n,a[i]+a[s.top()]); for(ii x:query[i]) { ans[x.se]=get(1,1,n,i,x.fi); } s.push(i); } for(int i=1;i<=q;i++)cout<<ans[i]<<'\n'; cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ; }

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...