oj.uz

Submission #238578

# Submission time Handle Problem Language Result Execution time Memory
238578 2020-06-12T01:09:54 Z jhnah917 medians (balkan11_medians) C++14
100 / 100
 52 ms 3836 KB 
#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.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 14 ms 896 KB Output is correct
5 Correct 20 ms 1408 KB Output is correct
6 Correct 36 ms 2552 KB Output is correct
7 Correct 52 ms 3836 KB Output is correct