Submission #61593279

---

Source Code Expand

#include<bits/stdc++.h>
namespace IO{
    template<typename T>
    void read(T &x){
        char ch=getchar();int fl=1;x=0;
        while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getchar();}
        while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
        x*=fl;
    }
    template<typename T,typename ...Args>
    void read(T &x,Args& ...args){
        read(x);read(args...);
    }
    template <typename _Tp>
    void write(_Tp x) {
        if(x<0) x=(~x+1),putchar('-');
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
}
using namespace std;
using namespace IO;
const int N=5e5+5,mod=1e9+7,Inf=1e9;
int n,q,a[N],b[N],tot,rt[N];
struct PerSgtTree {
    #define mid ((l+r)>>1)
    int sum[N<<6],ls[N<<6],rs[N<<6],cnt;
    void modify(int &x,int p,int l,int r,int pos) {
        x=++cnt;
        sum[x]=sum[p]+1;
        ls[x]=ls[p]; rs[x]=rs[p];
        if(l==r) return ;
        if(pos<=mid) modify(ls[x],ls[p],l,mid,pos);
        else modify(rs[x],rs[p],mid+1,r,pos);
    }
    int query(int A,int B,int l,int r,int k) {
        if(l>=r) return l;
        int res=sum[ls[A]]-sum[ls[B]];
        if(res<k) return query(rs[A],rs[B],mid+1,r,k-res);
        else return query(ls[A],ls[B],l,mid,k);
    }
    int find(int A,int B,int l,int r,int k) {
        // printf("%d %d\n",l,r);
        if(l==r) return sum[A]-sum[B];
        int res=sum[rs[A]]-sum[rs[B]];
        if(k<=mid) return find(ls[A],ls[B],l,mid,k)+res;
        else return find(rs[A],rs[B],mid+1,r,k);
    }
}T;
int solve(int L,int R) {
    int l=1,r=(R-L+1)/2,ans=0;
    while(l<=r) {
        int Mid=(l+r)>>1;
        int p=T.query(rt[R],rt[L-1],1,Inf,Mid);
        int num=T.find(rt[R],rt[L-1],1,Inf,p*2);
        printf("%d %d %d\n",Mid,p,num);
        if(num>=Mid) l=Mid+1,ans=Mid;
        else r=Mid-1;
    }
    return ans;
}
int cmp(int x,int y) {
    return x<y;
} 
int check(int x) {
    for(int i=1;i<=x;i++) {
        int to=n-x+i;
        if(a[i]*2>a[to]) return 0;
    }
    return 1;
}
signed main() {
#ifndef KAxdd
#ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#endif
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+n+1,cmp);
    int l=1,r=n/2,ans=0;
    while(l<=r) {
        int Mid=(l+r)>>1;
        if(check(Mid)) l=Mid+1,ans=Mid;
        else r=Mid-1;
    }
    printf("%d\n",ans);
    // for(int i=1;i<=n;i++) T.modify(rt[i],rt[i-1],1,Inf,a[i]);
    // read(q);
    // while(q--) {
    //     int l,r; read(l,r);
    //     printf("%lld\n",solve(l,r));
    // }
    return 0;
}
/*
11
1 1 2 3 4 4 7 10 11 12 20
1
1 11

*/

Submission Info

Judge Result