Submission #1190733

#TimeUsernameProblemLanguageResultExecution timeMemory
1190733sasdeTriple Jump (JOI19_jumps)C++20
100 / 100
716 ms78392 KiB
#include<bits/stdc++.h> #define task "strdel" #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define se second #define fi first #define ffi fi.fi #define sfi se.fi #define sse se.se #define fse fi.se #define lt(i, c, d) for(int i = c; i <= d; ++i) #define fl(i, c, d) for(int i = d; i >= c; --i) #define pb push_back #define emb emplace_back #define emf emplace_front #define em emplace using namespace std; const int N=1e6+5,lg=20,mod=1e9+7; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int u,int v){ return u+rd()%(v-u+1); } #define int long long int a[N],n,q; struct pt { int st[N*4],lazy[N*4],val1[N*4]; void build(int id,int r,int l){ if(r==l){ val1[id]=a[r]; st[id]=-1e18; return; } int mid=(r+l)>>1; build(id<<1,r,mid); build(id<<1|1,mid+1,l); val1[id]=max(val1[id<<1],val1[id<<1|1]); st[id]=max(st[id<<1],st[id<<1|1]); } void down(int id){ if(lazy[id]==0)return; lazy[id<<1]=max(lazy[id],lazy[id<<1]); lazy[id<<1|1]=max(lazy[id<<1|1],lazy[id]); st[id<<1]=max(st[id<<1],lazy[id]+val1[id<<1]); st[id<<1|1]=max(st[id<<1|1],lazy[id]+val1[id<<1|1]); lazy[id]=0; } void update(int id,int r,int l,int u,int v,int val){ if(r>v||l<u)return; if(r>=u&&l<=v){ st[id]=max(st[id],val1[id]+val); lazy[id]=max(lazy[id],val); return ; } down(id); int mid=(r+l)>>1; update(id<<1,r,mid,u,v,val); update(id<<1|1,mid+1,l,u,v,val); st[id]=max(st[id<<1],st[id<<1|1]); } int get(int id,int r,int l,int u,int v){ if(r>v||l<u)return -1e18; if(r>=u&&l<=v){ return st[id]; } down(id); int mid=(r+l)>>1; return max(get(id<<1,r,mid,u,v),get(id<<1|1,mid+1,l,u,v)); } }it; vector<ii>res[N]; int ans[N]; void solve(){ cin >> n; for(int i=1;i<=n;++i)cin >> a[i]; cin >> q; for(int i=1;i<=q;++i){ int u,v; cin >> u >> v; res[u].emb(v,i); }it.build(1,1,n); stack<int>s; for(int i=n;i>=1;--i){ while(!s.empty()&&a[s.top()]<=a[i]){ it.update(1,1,n,2*s.top()-i,n,a[i]+a[s.top()]); s.pop(); } if(!s.empty()){ it.update(1,1,n,2*s.top()-i,n,a[i]+a[s.top()]); } s.push(i); for(ii j:res[i]){ ans[j.se]=it.get(1,1,n,i,j.fi); } } for(int i=1;i<=q;++i)cout << ans[i]<<'\n'; } main() { srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int t=1; // cin >> t; while(t--){ solve(); } }

Compilation message (stderr)

jumps.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | main()
      | ^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:109:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:110:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |       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...