Submission #18066012

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],s[100005],tree[200015];
void add(int x,int y){x+=100000;for(int i=x;i<=200005;i+=(i&(-i)))tree[i]+=y;}
int ask(int x){x+=100000;int res=0;for(int i=x;i;i-=(i&(-i)))res+=tree[i];return res;}
bool check(int x)//median<=x
{
    memset(tree,0,sizeof(tree));
    add(1,1);
    int nows=0;
    long long res=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=x)nows++;
        res+=ask(2*nows-i);
        add(2*nows-i+1,1);
    }
    return res>=1ll*n*(n+1)/4+1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int t=unique(b+1,b+n+1)-(b+1);
    int l=1,r=t;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(b[mid]))r=mid;
        else l=mid+1;
    }
    printf("%d",b[l]);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:22:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
./Main.cpp:23:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   23 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
      |                          ~~~~~^~~~~~~~~~~~

Judge Result