Submission #90591

#	Time	Username	Problem	Language	Result	Execution time	Memory
90591		314rate	medians (balkan11_medians)	C++14	100 / 100	103 ms	13732 KiB

medians

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N=2*100000+5;

int n;
int b[N];
bool viz[N];
int v[N];

int aib[N];

void add(int p,int x)
{
    for(int i=p;i<N;i+=i&(-i))
    {
        aib[i]+=x;
    }
}

int prefix(int p)
{
    int a=0;
    for(int i=p;i>=1;i-=i&(-i))
    {
        a+=aib[i];
    }
    return a;
}

set<int>lft;

void upd(int i,int x)
{
    viz[x]=1;
    v[i]=x;
    add(x,1);
    lft.erase(x);
}

int small(int x)
{
    return prefix(x-1);
}

int big(int x)
{
    return prefix(N-1)-prefix(x);
}

int mi()
{
    auto it=lft.begin();
    return *it;
}

int ma()
{
    auto it=lft.end();
    it--;
    return *it;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //  freopen("medians.in","r",stdin);
  //  freopen("medians.out","w",stdout);
    cin>>n;
    for(int i=1;i<=2*n-1;i++)
    {
        lft.insert(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    upd(1,b[1]);
    for(int i=2;i<=n;i++)
    {
        int p=2*i-2;
        int x=b[i];
        if(viz[x]==0)
        {
            upd(p++,x);
        }
        int a=small(x);
        int b=big(x);
        if(a==b)
        {
            upd(p++,mi());
            upd(p++,ma());
        }
        while(a<b)
        {
            upd(p++,mi());
            a++;
        }
        while(a>b)
        {
            upd(p++,ma());
            b++;
        }
        if(p!=2*i)
        {
            while(1) {}
        }
    }
    for(int i=1;i<=2*n-1;i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<"\n";
    return 0;
}
/**


1     3     3     4     5
1  ?  3  ?  ?  ?  ?  ?  ?
1  9  3  2  4  8  7  5  6


f(i) = i / 2

info (i)
:
 x;
 exista x
 f(i) < x
 f(i) > x


**/

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35