Submission #360200

#TimeUsernameProblemLanguageResultExecution timeMemory
360200kiomiTriple Jump (JOI19_jumps)C++14
0 / 100
25 ms3200 KiB
//order_of_key(k): Number of items strictly smaller than k . //find_by_order(k): K-th element in a set (counting from zero). #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define full(x,n) x,x+n+1 #define full(x) x.begin(),x.end() #define finish return 0 #define putb push_back #define f first #define s second //logx(a^n)=loga(a^n)/logx(a) //logx(a*b)=logx(a)+logx(b) //logx(y)=log(y)/log(x) //logb(n)=loga(n)/loga(b) #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define putf push_front #define gainb pop_back //(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n //(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i #define gainf pop_front #define len(x) (int)x.size() // 1/b%mod=b^(m-2)%mod // (a>>x)&1==0 // a^b=(a+b)-2(a&b) typedef double db; typedef long long ll; //sum of squares n*(n+1)*(2n+1)/6 //sum of cubes [n*(n+1)/2]^2 //sum of squares for odds n*(4*n*n-1)/3 //sum of cubes for odds n*n*(2*n*n-1) const int ary=5e5+5; const int mod=1e9+7; const ll inf=1e18; using namespace std; using namespace __gnu_pbds; int n,a[ary],q,t[4*ary]; ll ans; void build(int v=1,int tl=1,int tr=n){ if(tl==tr){ t[v]=a[tl]; return; } int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v]=max(t[v*2],t[v*2+1]); } pair<int,int> getL(int l,int r,int v=1,int tl=1,int tr=n){ if(r<tl||tr<l){ return {0,0}; } int tm=(tl+tr)/2; if(l<=tl&&tr<=r){ if(tl==tr){ return {tl,a[tl]}; } if(t[v*2]>=t[v*2+1]){ return getL(l,r,v*2,tl,tm); } return getL(l,r,v*2+1,tm+1,tr); } pair<int,int> x=getL(l,r,v*2,tl,tm); pair<int,int> y=getL(l,r,v*2+1,tm+1,tr); if(x.s>=y.s){ return x; } return y; } pair<int,int> getR(int l,int r,int v=1,int tl=1,int tr=n){ if(r<tl||tr<l){ return {0,0}; } int tm=(tl+tr)/2; if(l<=tl&&tr<=r){ if(tl==tr){ return {tl,a[tl]}; } if(t[v*2]<=t[v*2+1]){ return getR(l,r,v*2+1,tm+1,tr); } return getR(l,r,v*2,tl,tm); } pair<int,int> x=getR(l,r,v*2,tl,tm); pair<int,int> y=getR(l,r,v*2+1,tm+1,tr); if(x.s<=y.s){ return y; } return x; } void sana(int l,int r,pair<int,ll> ip,pair<int,ll> id){ if(ip.f>l){ ans=max(ans,id.s+ip.s+getL(max(l,ip.f-id.f+ip.f),ip.f-1).s); } if(ip.f+1<id.f){ ans=max(ans,id.s+ip.s+getL(ip.f+1,ip.f+(id.f-ip.f)/2).s); } if(id.f+id.f-ip.f<=r){ ans=max(ans,id.s+ip.s+getL(id.f+id.f-ip.f,r).s); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } build(); cin>>q; while(q--){ ans=0; int l,r; cin>>l>>r; pair<int,ll> id=getL(l,r),ip; if(id.f>l){ ip=getL(l,id.f-1); sana(l,r,ip,id); ip=getR(l,id.f-1); sana(l,r,ip,id); } if(id.f<r){ ip=getL(id.f+1,r); sana(l,r,id,ip); ip=getR(id.f+1,r); sana(l,r,id,ip); } id=getR(l,r); if(id.f>l){ ip=getL(l,id.f-1); sana(l,r,ip,id); ip=getR(l,id.f-1); sana(l,r,ip,id); } if(id.f<r){ ip=getL(id.f+1,r); sana(l,r,id,ip); ip=getR(id.f+1,r); sana(l,r,id,ip); } cout<<ans<<"\n"; } }

Compilation message (stderr)

jumps.cpp:7: warning: "full" redefined
    7 | #define full(x) x.begin(),x.end()
      | 
jumps.cpp:6: note: this is the location of the previous definition
    6 | #define full(x,n) x,x+n+1
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...