제출 #203937

#제출 시각아이디문제언어결과실행 시간메모리
203937SegtreeGap (APIO16_gap)C++14
0 / 100
57 ms1912 KiB
#include<iostream> #include<algorithm> #include<vector> #include"gap.h" using namespace std; typedef long long ll; #define chmin(a,b) a=min(a,b) #define chmax(a,b) a=max(a,b) #define rep(i,n) for(int i=0;i<n;i++) #define mod 1000000007 #define mad(a,b) a=(a+b)%mod /* ll a[100010],n,m; void MinMax(ll s,ll t,ll &mn,ll &mx){ m++; ll l,r,mid; l=-1,r=n; while(l<r-1){ mid=(l+r)>>1; if(a[mid]>=s)r=mid; else l=mid; } mn=a[r]; l=-1,r=n; while(l<r-1){ mid=(l+r)>>1; if(a[mid]<=t)l=mid; else r=mid; } mx=a[l]; }*/ ll findGap(int T,int N){ ll A[100010]; A[0]=-1,A[N+1]=2e18; ll mn,mx; MinMax(A[0]+1,A[N+1]-1,&mn,&mx); A[1]=mn,A[N]=mx; for(int i=1;i<=N-1;i++){ MinMax(A[i]+1,A[i]+1,&mn,&mx); A[i+1]=mn; } //for(int i=0;i<=N+1;i++)cout<<i<<":"<<A[i]<<endl; ll ans=0; for(int i=1;i<=N-1;i++)ans=max(ans,A[i+1]-A[i]); return ans; } /* int main(){ n=100000; rep(i,n)a[i]=rand()%mod; sort(a,a+n); ll ans=0; rep(i,n-1)chmax(ans,a[i+1]-a[i]); m=0; cout<<ans<<endl; cout<<findGap(0,n)<<endl; cout<<"m="<<m<<endl; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...