oj.uz

Submission #90591

# Submission time Handle Problem Language Result Execution time Memory
90591 2018-12-22T18:14:51 Z 314rate medians (balkan11_medians) C++14
100 / 100
 103 ms 13732 KB 
#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.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 516 KB Output is correct
3 Correct 2 ms 516 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 804 KB Output is correct
11 Correct 2 ms 804 KB Output is correct
12 Correct 2 ms 804 KB Output is correct
13 Correct 3 ms 804 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1064 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 7 ms 1760 KB Output is correct
4 Correct 14 ms 2840 KB Output is correct
5 Correct 30 ms 4984 KB Output is correct
6 Correct 62 ms 8996 KB Output is correct
7 Correct 103 ms 13732 KB Output is correct