oj.uz

Submission #843072

# Submission time Handle Problem Language Result Execution time Memory
843072 2023-09-03T15:49:49 Z fanwen Abracadabra (CEOI22_abracadabra) C++17
35 / 100
 211 ms 29752 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

template <class T> struct Fenwick_Tree {
    vector<T> bit;
    int n, LOG;
    Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5) {
        this->LOG = 32 - __builtin_clz(n);
    }

    void clear() { fill(bit.begin(), bit.end(), T(0)); }

    void update(int u, T val) {
        // cout << u << " " << val << '\n';
        for (; u <= n; u += u & -u) bit[u] += val;
    }

    T get(int u) {
        T ans = 0;
        assert(u <= n);
        for (; u; u -= u & -u) ans += bit[u];
        return ans;
    }

    T get(int l, int r) {
        return get(r) - get(l - 1);
    }

    int lower_bound(T x) {
        int pos = 0;
        for (int k = LOG - 1; k >= 0; --k) {
            if(pos + (1 << k) <= n && bit[pos + (1 << k)] < x) {
                pos ^= 1 << k;
                x -= bit[pos];
            }
        }
        return pos + 1;
    }
};

const int MAXN = 1e5 + 5;

int N, Q, a[MAXN], p[MAXN], ans[MAXN * 10], nxt[MAXN];
vector <pair <int, int>> queries[MAXN];

void you_make_it(void) {
    cin >> N >> Q;
    FOR(i, 1, N) cin >> a[i], p[a[i]] = i;
    FOR(i, 1, Q) {
        int t, x; cin >> t >> x;
        queries[min(t, N)].emplace_back(x, i);
    }
    stack <int> st;
    st.push(N + 1), a[N + 1] = N + 1;
    FORD(i, N, 1) {
        while(!st.empty() and a[st.top()] <= a[i]) st.pop();
        nxt[i] = st.top();
        st.push(i);
    }
    for (auto [x, i] : queries[0]) ans[i] = a[x];
    int lt = 1;
    Fenwick_Tree <int> bit(N);
    while(lt <= N / 2) {
        bit.update(a[lt], min(N / 2 + 1, nxt[lt]) - lt);
        lt = nxt[lt];
    }
    lt = N / 2 + 1;
    while(lt <= N) {
        bit.update(a[lt], min(N + 1, nxt[lt]) - lt);
        lt = nxt[lt];
    }
    // exit(0);
    FOR(q, 1, N) {
        for (auto [x, i] : queries[q]) {
            int id = bit.lower_bound(x);
            ans[i] = a[x - bit.get(id - 1) + p[id] - 1];
        }
        int id = bit.lower_bound(N / 2);
        if(bit.get(id) <= N / 2) continue;

        int lt = N / 2 - bit.get(id - 1) + p[id];
        int rt = bit.get(id, id) + p[id] - 1;
        bit.update(id, N / 2 - bit.get(id));
        while(lt <= rt) {
            bit.update(a[lt], min(rt + 1, nxt[lt]) - lt);
            lt = nxt[lt];
        }
    }
    FOR(i, 1, Q) cout << ans[i] << '\n';
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    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

Main.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
Main.cpp:76:29:   required from here
Main.cpp:20:9: warning: 'Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
   20 |     int n, LOG;
      |         ^
Main.cpp:19:15: warning:   'std::vector<int> Fenwick_Tree<int>::bit' [-Wreorder]
   19 |     vector<T> bit;
      |               ^~~
Main.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5) {
      |     ^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 21268 KB Output is correct
2 Correct 211 ms 27484 KB Output is correct
3 Correct 204 ms 26700 KB Output is correct
4 Correct 157 ms 25412 KB Output is correct
5 Correct 171 ms 28864 KB Output is correct
6 Correct 168 ms 28520 KB Output is correct
7 Correct 194 ms 29752 KB Output is correct
8 Correct 160 ms 27244 KB Output is correct
9 Correct 161 ms 25972 KB Output is correct
10 Correct 162 ms 25940 KB Output is correct
11 Correct 171 ms 26532 KB Output is correct
12 Correct 172 ms 23788 KB Output is correct
13 Correct 161 ms 25088 KB Output is correct
14 Correct 170 ms 27968 KB Output is correct
15 Correct 177 ms 25620 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 141 ms 24128 KB Output is correct
18 Correct 146 ms 23728 KB Output is correct
19 Correct 1 ms 4744 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 10820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8528 KB Output is correct
2 Correct 49 ms 8280 KB Output is correct
3 Correct 46 ms 8284 KB Output is correct
4 Correct 35 ms 7764 KB Output is correct
5 Correct 39 ms 8272 KB Output is correct
6 Correct 34 ms 7760 KB Output is correct
7 Correct 38 ms 8016 KB Output is correct
8 Correct 36 ms 7760 KB Output is correct
9 Correct 50 ms 8016 KB Output is correct
10 Correct 30 ms 7692 KB Output is correct
11 Correct 33 ms 7760 KB Output is correct
12 Correct 36 ms 7504 KB Output is correct
13 Correct 31 ms 7508 KB Output is correct
14 Correct 32 ms 7760 KB Output is correct
15 Correct 30 ms 7512 KB Output is correct
16 Correct 11 ms 5720 KB Output is correct
17 Correct 27 ms 7380 KB Output is correct
18 Correct 25 ms 7124 KB Output is correct
19 Correct 1 ms 4696 KB Output is correct
20 Correct 1 ms 4696 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 21268 KB Output is correct
2 Correct 211 ms 27484 KB Output is correct
3 Correct 204 ms 26700 KB Output is correct
4 Correct 157 ms 25412 KB Output is correct
5 Correct 171 ms 28864 KB Output is correct
6 Correct 168 ms 28520 KB Output is correct
7 Correct 194 ms 29752 KB Output is correct
8 Correct 160 ms 27244 KB Output is correct
9 Correct 161 ms 25972 KB Output is correct
10 Correct 162 ms 25940 KB Output is correct
11 Correct 171 ms 26532 KB Output is correct
12 Correct 172 ms 23788 KB Output is correct
13 Correct 161 ms 25088 KB Output is correct
14 Correct 170 ms 27968 KB Output is correct
15 Correct 177 ms 25620 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 141 ms 24128 KB Output is correct
18 Correct 146 ms 23728 KB Output is correct
19 Correct 1 ms 4744 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Runtime error 11 ms 10820 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -