oj.uz

Submission #885133

# Submission time Handle Problem Language Result Execution time Memory
885133 2023-12-09T04:05:52 Z fanwen medians (balkan11_medians) C++17
100 / 100
 80 ms 12968 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

template <class T> struct Fenwick_Tree {
    vector<T> bit;
    int n;
    Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
    
    void clear() { fill(bit.begin(), bit.end(), T(0)); }

    void update(int u, T val) {
        for (; u <= n; u += u & -u) bit[u] += val;
    }
    
    T get(int u) {
        T ans = 0;
        for (; u; u -= u & -u) ans += bit[u];
        return ans; 
    }
    
    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
};


const int MAX = 1e5 + 5;

int n, a[MAX];

set <int> s;

void pans(int x) {
    cout << x << " ";
    
}

void you_make_it(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < 2 * n; ++i) s.insert(i);
    Fenwick_Tree <int> fen(n << 1 | 1);

    auto pans = [&] (int val) {
        cout << val << " ";
        fen.update(val, 1);
        s.erase(val);        
    };
    for (int i = 1; i <= n; ++i) {
        if(s.find(a[i]) != s.end()) {
            pans(a[i]);
        }
        while(fen.get(a[i]) < i) {
            pans(*s.begin());
        }

        while(fen.get(a[i], n << 1 | 1) < i) {
            pans(*--s.end());
        }
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("median");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

medians.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
medians.cpp:47:38:   required from here
medians.cpp:11:9: warning: 'Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
   11 |     int n;
      |         ^
medians.cpp:10:15: warning:   'std::vector<int> Fenwick_Tree<int>::bit' [-Wreorder]
   10 |     vector<T> bit;
      |               ^~~
medians.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
      |     ^~~~~~~~~~~~
medians.cpp: In function 'int main()':
medians.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
medians.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("median");
      |     ^~~~
medians.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
medians.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("median");
      |     ^~~~

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 6 ms 1348 KB Output is correct
4 Correct 12 ms 2392 KB Output is correct
5 Correct 24 ms 4184 KB Output is correct
6 Correct 52 ms 8276 KB Output is correct
7 Correct 80 ms 12968 KB Output is correct