Submission #238578

#	Time	Username	Problem	Language	Result	Execution time	Memory
238578		jhnah917	medians (balkan11_medians)	C++14	100 / 100	52 ms	3836 KiB

medians

#include <bits/stdc++.h>
using namespace std;

unsigned n, t, prv;
struct Seg{
    int tree[1u << 19u]{};
    const unsigned sz = 1u << 18u;
    void insert(unsigned x){
        x |= sz; tree[x]++;
        while(x >>= 1u) tree[x]++;
    }
    void erase(unsigned x){
        x |= sz; tree[x]--;
        while(x >>= 1u) tree[x]--;
    }
    int count(unsigned x){ return tree[x | sz]; }
    unsigned begin(){
        unsigned x = 1;
        while(x < sz){
            if(tree[x << 1u]) x <<= 1u;
            else x = x << 1u | 1u;
        }
        return x - sz;
    }
    unsigned rbegin(){
        unsigned x = 1;
        while(x < sz){
            if(tree[x << 1u | 1u]) x = x << 1u | 1u;
            else x <<= 1u;
        }
        return x - sz;
    }
}st;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> t;
    for(unsigned i=1; i<n+n; i++) if(i ^ t) st.insert(i);
    cout << t << " "; prv = t;
    for(unsigned i=1; i<n; i++){
        cin >> t;
        if(st.count(t)){
            cout << t << " "; st.erase(t);
            unsigned v = t < prv ? st.begin() : st.rbegin();
            cout << v << " "; st.erase(v); prv = t; continue;
        }
        unsigned v = t <= prv ? st.begin() : st.rbegin();
        cout << v << " "; st.erase(v);
        v = t < prv ? st.begin() : st.rbegin();
        cout << v << " "; st.erase(v);
        prv = t;
    }
}

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