Submission #375288

#TimeUsernameProblemLanguageResultExecution timeMemory
375288kiomiPo (COCI21_po)C++17
60 / 70
1099 ms3948 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 f first #define s second #define len(x) (int)x.size() //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> //(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 // 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=1e6+5; //const int mod=1e9+7; const ll inf=1e18; using namespace std; using namespace __gnu_pbds; int n,a[ary],t[4*ary],tp[4*ary],mod[4*ary],ans; void build(int v=1,int tl=1,int tr=n){ if(tl==tr){ t[v]=tp[v]=a[tl]; return; } int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v]=min(t[v*2],t[v*2+1]); tp[v]=max(tp[v*2],tp[v*2+1]); } void push(int v,bool ok){ if(mod[v]){ t[v]-=mod[v]; tp[v]-=mod[v]; if(ok){ mod[v*2]+=mod[v]; mod[v*2+1]+=mod[v]; } mod[v]=0; } } void upd(int l,int r,int x,int v=1,int tl=1,int tr=n){ push(v,(tl<tr)); if(r<tl||tr<l){ return; } if(l<=tl&&tr<=r){ mod[v]+=x; push(v,(tl<tr)); return; } int tm=(tl+tr)/2; upd(l,r,x,v*2,tl,tm); upd(l,r,x,v*2+1,tm+1,tr); t[v]=min(t[v*2],t[v*2+1]); tp[v]=max(tp[v*2],tp[v*2+1]); } int getmn(int l,int r,int v=1,int tl=1,int tr=n){ push(v,(tl<tr)); if(r<tl||tr<l||r<l){ return 1e9+7; } if(l<=tl&&tr<=r){ return t[v]; } int tm=(tl+tr)/2; return min(getmn(l,r,v*2,tl,tm),getmn(l,r,v*2+1,tm+1,tr)); } int getmx(int l,int r,int v=1,int tl=1,int tr=n){ push(v,(tl<tr)); if(r<tl||tr<l||r<l){ return 0; } if(l<=tl&&tr<=r){ return tp[v]; } int tm=(tl+tr)/2; return max(getmx(l,r,v*2,tl,tm),getmx(l,r,v*2+1,tm+1,tr)); } 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(); while(1){ int u=0; int l=1,r=n; while(l<=r){ int m=(l+r)/2; if(getmx(1,m)){ r=m-1; u=m; } else{ l=m+1; } } if(!u){ break; } ans++; l=u,r=n; int v=u; while(l<=r){ int m=(l+r)/2; if(getmn(u,m)){ l=m+1; v=m; } else{ r=m-1; } } upd(u,v,getmn(u,v)); } cout<<ans; }

Compilation message (stderr)

Main.cpp:7: warning: "full" redefined
    7 | #define full(x) x.begin(),x.end()
      | 
Main.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...