Submission #1029039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029039		lucri	medians (balkan11_medians)	C++17	5 / 100	160 ms	2132 KiB

medians

#include <iostream>
using namespace std;
int n,ant,act;
bool aint[800010];
void blocheaza(int poz,int b,int e,int pozu)
{
    if(pozu<b||pozu>e)
        return;
    if(b==e)
    {
        aint[poz]=true;
        return;
    }
    blocheaza(poz*2,b,(b+e)/2,pozu);
    blocheaza(poz*2+1,(b+e)/2+1,e,pozu);
    aint[poz]=(aint[poz*2]&aint[poz*2+1]);
}
int maxim(int poz,int b,int e)
{
    if(b==e)
        return b;
    if(aint[poz*2+1]==false)
        return maxim(poz*2+1,(b+e)/2+1,e);
    return maxim(poz*2,b,(b+e)/2);
}
int minim(int poz,int b,int e)
{
    if(b==e)
        return b;
    if(aint[poz*2]==false)
        return minim(poz*2,b,(b+e)/2);
    return minim(poz*2+1,(b+e)/2+1,e);
}
int main()
{
    cin>>n>>ant;
    cout<<ant<<' ';
    blocheaza(1,1,2*n-1,ant);
    for(int i=2;i<=n;++i)
    {
        cin>>act;
        if(act>ant)
        {
            cout<<act<<' ';
            blocheaza(1,1,2*n-1,act);
            ant=maxim(1,1,2*n-1);
            cout<<ant<<' ';
            blocheaza(1,1,2*n-1,ant);
        }
        else if(act<ant)
        {
            cout<<act<<' ';
            blocheaza(1,1,2*n-1,act);
            ant=minim(1,1,2*n-1);
            cout<<ant<<' ';
            blocheaza(1,1,2*n-1,ant);
        }
        else
        {
            ant=minim(1,1,2*n-1);
            cout<<ant<<' ';
            blocheaza(1,1,2*n-1,ant);
            ant=maxim(1,1,2*n-1);
            cout<<ant<<' ';
            blocheaza(1,1,2*n-1,ant);
        }
        ant=act;
    }
    return 0;
}

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