Submission #1214070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214070		nqknht	medians (balkan11_medians)	C++20	15 / 100	1093 ms	21260 KiB

medians

#include <bits/stdc++.h>

#define ll long long

const ll I = 2e5 + 9;

using namespace std;

set<int> smaller, bigger;
int BIT[I], ans[I], a[I], n, pos;
bool mark[I];

void update(int pos)
{
    for (; pos <= 2 * n - 1; pos += pos & (-pos))
        BIT[pos]++;
}

int get(int pos)
{
    int rs = 0;
    for (; pos > 0; pos -= pos & (-pos))
        rs += BIT[pos];
    return rs;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= 2 * n - 1; i++)
    {
        smaller.insert(i);
        bigger.insert(i);
    }
    smaller.erase(a[1]);
    bigger.erase(a[1]);
    ans[1] = a[1];
    mark[a[1]] = true;
    update(a[1]);
    pos = 1;
    for (int i = 2; i <= n; i++)
    {

        int lf = get(a[i]), rt = i * 2 - 3 - lf;
        // cout << lf << " " << rt << " " << i << " \n";
        if (mark[a[i]] == false)
        {
            pos++;
            ans[pos] = a[i];
            update(a[i]);
            mark[a[i]] = true;
            smaller.erase(a[i]);
            bigger.erase(a[i]);
            lf++;
        }
        while (lf < i)
        {
            auto id = smaller.begin();
            pos++;
            ans[pos] = *id;
            mark[(*id)] = true;
            update((*id));
            smaller.erase(*id);
            bigger.erase(*id);
            lf++;
        }
        while (rt < i - 1)
        {
            auto id = bigger.lower_bound(a[i]);
            pos++;
            ans[pos] = *id;
            mark[(*id)] = true;
            update((*id));
            smaller.erase(*id);
            bigger.erase(*id);
            rt++;
        }
    }
    for (int i = 1; i <= 2 * n - 1; i++)
        cout << ans[i] << " ";
    return 0;
}

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