Submission #295807

#TimeUsernameProblemLanguageResultExecution timeMemory
295807GajowyTriple Jump (JOI19_jumps)C++14
100 / 100
1085 ms107384 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define mp make_pair #define eb emplace_back #define pb push_back #define e1 first #define e2 second #define int int_fast32_t #define uint uint_fast64_t #define ll int_fast64_t #define ull uint_fast64_t #define int16 int_fast16_t #define uint16 uint_fast16_t #define int32 int_fast32_t #define uint32 uint_fast32_t #define int64 int_fast64_t #define uint64 uint_fast64_t #define ld long double #define float long double #define size(x) (int)x.size() #define satori int testCases; cin>>testCases; while(testCases--) #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define all(r) begin(r),end(r) #define rall(r) rbegin(r),rend(r) #define time chrono::high_resolution_clock().now().time_since_epoch().count() #define elapsed(__begin,__end) (__end-__begin)/CLOCKS_PER_SEC typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; float pi=3.14159265358979323846; const int MAXN=5e5+10,base=(1<<19),inf=1e9+2137; int ans[MAXN],a[MAXN],b[base*2],c[base*2],bc[base*2]; vector<int> ud[MAXN],s; vector<pair<int,int>> qr[MAXN]; void add(int u,int v) { u+=base; while(u) { b[u]=max(b[u],v),u/=2; bc[u]=max({bc[u],bc[u*2],bc[u*2+1],b[u*2]+c[u*2+1]}); } } pair<int,pair<int,int>> get(int l,int r,int u=1,int cl=0,int cr=base-1) { if(cl>r||cr<l) return mp(-inf,mp(-inf,-inf)); if(cl>=l&&cr<=r) return mp(bc[u],mp(b[u],c[u])); auto lo=get(l,r,u*2,cl,(cl+cr)/2),hi=get(l,r,u*2+1,(cl+cr)/2+1,cr); return mp(max({lo.e1,hi.e1,lo.e2.e1+hi.e2.e2}),mp(max(lo.e2.e1,hi.e2.e1),max(lo.e2.e2,hi.e2.e2))); } int32_t main() { fastio; int n,q,l,r; cin>>n; for(int i=base;i<base*2;i++) c[i]=-inf; for(int i=1;i<=n;i++) { cin>>a[i]; c[base+i]=a[i]; while(size(s)&&a[s.back()]<a[i]) ud[s.back()].eb(i),s.pop_back(); if(size(s)) ud[s.back()].eb(i); if(size(s)&&a[s.back()]==a[i]) s.pop_back(); s.eb(i); } cin>>q; for(int i=0;i<q;i++) cin>>l>>r,qr[l].eb(mp(r,i)); for(int i=0;i<base*2;i++) b[i]=bc[i]=-inf; for(int i=base-1;i>=0;i--) c[i]=max(c[i*2],c[i*2+1]); for(int i=n;i>=1;i--) { for(auto xd:ud[i]) { r=xd; if(r*2-i>n) continue; add(r*2-i-1,a[i]+a[r]); } for(auto xd:qr[i]) ans[xd.e2]=get(i,xd.e1).e1; } for(int i=0;i<q;i++) cout<<ans[i]<<'\n'; }

Compilation message (stderr)

jumps.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
jumps.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...