Submission #722347

#	Time	Username	Problem	Language	Result	Execution time	Memory
722347		groshi	medians (balkan11_medians)	C++17	100 / 100	163 ms	16052 KiB

medians

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,tree_order_statistics_node_update>
new_data_set;
int b[300000];
int wynik[300000];
set<int> mam;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    new_data_set secik;
    int n;
    cin>>n;
    for(int i=1;i<=2*n-1;i++)
        mam.insert(i);
    for(int i=1;i<=n;i++)
        cin>>b[i];
    int jestem=1;
    for(int i=1;i<=n;i++)
    {
        int mniejszych=i-1;
        int wiekszych=i-1;
        mniejszych-=(secik.order_of_key(b[i]));
        wiekszych-=(secik.size()-secik.order_of_key(b[i]+1));
        auto it=mam.begin();
        int ile1=mniejszych,ile2=wiekszych;
        while(mniejszych>0)
        {
            wynik[jestem]=*it;
            secik.insert(*it);
            it++;
            mniejszych--;
            jestem++;
        }
        it=mam.end();
        it--;
        while(wiekszych>0)
        {
            wynik[jestem]=*it;
            secik.insert(*it);
            it--;
            wiekszych--;
            jestem++;
        }
        while(ile1)
        {
            it=mam.begin();
            mam.erase(*it);
            ile1--;
        }
        while(ile2)
        {
            it=mam.end();
            it--;
            mam.erase(*it);
            ile2--;
        }
        if(mam.find(b[i])!=mam.end())
        {
            mam.erase(b[i]);
            secik.insert(b[i]);
            wynik[jestem]=b[i];
            jestem++;
        }
    }
    for(int i=1;i<=n*2-1;i++)
        cout<<wynik[i]<<" ";
    return 0;
}

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