Submission #372802

#	Time	Username	Problem	Language	Result	Execution time	Memory
372802		iliccmarko	medians (balkan11_medians)	C++14	0 / 100	125 ms	4708 KiB

medians

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
const int N = 2e5 + 50;
int seg[4*N];
int n;
int b[N];
vector<int> a;

void update(int node, int l, int r, int pos)
{
    if(l==r){
        seg[node] = 1;
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid) update(node*2+2, mid+1, r, pos);
    else update(node*2+1, l, mid, pos);
}

int get_sum(int node, int l, int r, int i, int j)
{
    if(i>r||j<r) return 0;
    if(i>=l&&j<=r) return seg[node];
    int mid = (i+j)/2;
    return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}



int main()
{
    ios
    cin>>n;
    for(int i = 0;i<n;i++) cin>>b[i];
    update(0, 0, 2*n, b[0]);
    a.pb(b[0]);
    int l = 1;
    if(b[0]==1) l++;
    int r = 2*n-1;
    if(b[0]==2*n-1) r--;
    for(int i = 1;i<n;i++)
    {
        int x = b[i];
        int cl = get_sum(0, 0, x-1, 0, 2*n);
        int cr = get_sum(0, x+1, 2*n, 0, 2*n);
        if(l==x) l++;
        if(r==x) r--;
        if(cl==cr)
        {
            while(get_sum(0, l, l, 0, 2*n)) l++;
            while(get_sum(0, r, r, 0, 2*n)) r--;
            a.pb(l);
            a.pb(r);
            update(0, 0, 2*n, l);
            update(0, 0, 2*n, r);
            l++;
            r--;
            while(get_sum(0, l, l, 0, 2*n)) l++;
            while(get_sum(0, r, r, 0, 2*n)) r--;
        }
        else if(cl>cr)
        {
            if(!get_sum(0, x, x, 0, 2*n))
            {
                while(get_sum(0, l, l, 0, 2*n)) l++;
            while(get_sum(0, r, r, 0, 2*n)) r--;
                a.pb(x);
                a.pb(r);
                update(0, 0, 2*n, x);
                update(0, 0, 2*n, r);
                r--;
                while(get_sum(0, r, r, 0, 2*n)) r--;
            }
            else
            {
                while(get_sum(0, l, l, 0, 2*n)) l++;
            while(get_sum(0, r, r, 0, 2*n)) r--;
                a.pb(r);
                update(0, 0, 2*n, r);
                r--;
                while(get_sum(0, r, r, 0, 2*n)) r--;
                update(0, 0, 2*n, r);
                a.pb(r);
                r--;
                while(get_sum(0, r, r, 0, 2*n)) r--;
            }
        }
        else
        {
            if(!get_sum(0, x, x, 0, 2*n))
            {
                while(get_sum(0, l, l, 0, 2*n)) l++;
            while(get_sum(0, r, r, 0, 2*n)) r--;
                a.pb(x);
                a.pb(l);
                update(0, 0, 2*n, x);
                update(0, 0, 2*n, l);
                l++;
                while(get_sum(0, l, l, 0, 2*n)) l++;
            }
            else
            {
                while(get_sum(0, l, l, 0, 2*n)) l++;
            while(get_sum(0, r, r, 0, 2*n)) r--;
                a.pb(l);
                update(0, 0, 2*n, l);
                l++;
                while(get_sum(0, l, l, 0, 2*n)) l++;
                update(0, 0, 2*n, l);
                a.pb(l);
                l++;
                while(get_sum(0, l, l, 0, 2*n)) l++;
            }
        }
    }

    for(int x : a)
        cout<<x<<" ";




    return 0;
}

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