Submission #1116311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116311		Zero_OP	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	433 ms	48200 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;

int N, Q, p[MAX], q[MAX], nxt[MAX];
vector<pair<int, int>> queries[MAX];

struct fenwick_tree{
    int L;
    vector<int> bit, ar;
    fenwick_tree(int n) : bit(n + 1, 0), ar(n + 1, 0), L(31 - __builtin_clz(n)) {}

    void update(int i, int v){
        for(; i < (int)bit.size(); i += i & (-i)) bit[i] += v;
    }

    int query(int i){
        int sum = 0;
        for(; i > 0; i -= i & (-i)) sum += bit[i];
        return sum;
    }

    int walk_first_lower(int k){ //first lower
        int pos = 0;
        for(int i = L; i >= 0; --i){
            if(pos + (1 << i) < (int)bit.size() && bit[pos + (1 << i)] < k){
                k -= bit[pos + (1 << i)];
                pos += (1 << i);
            }
        }
        return pos;
    }
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> Q;
    for(int i = 1; i <= N; ++i){
        cin >> p[i];
        q[p[i]] = i;
    }

    for(int i = 0; i < Q; ++i){
        int t, v;
        cin >> t >> v;
        queries[min(t, N)].emplace_back(v, i);
    }

    stack<int> st;
    for(int i = N; i >= 1; --i){
        while(!st.empty() && p[i] > p[st.top()]) st.pop();
        nxt[i] = (st.empty() ? N + 1 : st.top());
        st.push(i);
    }

    fenwick_tree ft(N);

    for(int i = 1; i <= N; i = nxt[i]){
        ft.update(p[i], nxt[i] - i);
    }

    auto get_kth = [&](int kth){
        int head = ft.walk_first_lower(kth) + 1;
        int sum_sizes = ft.query(head - 1);
        assert(sum_sizes < kth);
        return p[q[head] + kth - sum_sizes - 1];
    };

    bool demand = true;

    auto simulate = [&](){
        //info p[N/2]
        int head = ft.walk_first_lower(N / 2) + 1;
        int sum_sizes = ft.query(head);
        if(sum_sizes == N / 2) {
            demand = false;
            return; //[N/2] and [N/2+1] are in different blocks
        }

        //phase 1 : cut the left part
        int sum_previous_sizes = ft.query(head - 1);
        int current_block_size = sum_sizes - sum_previous_sizes;
        int position_head = q[head];
        int left_part_cut_size = N / 2 - sum_previous_sizes;
        ft.update(head, -current_block_size + left_part_cut_size);

        //phase 2 : divide the right part into some smaller blocks
        int new_head = p[q[head] + left_part_cut_size];
        int cur = N / 2;
        int old_bound = sum_sizes;

        int i;
        for(i = q[new_head]; cur + nxt[i] - i < old_bound; i = nxt[i]){
            ft.update(p[i], nxt[i] - i);
            cur += nxt[i] - i;
        }

        ft.update(p[i], old_bound - cur);
    };

    vector<int> ans(Q);
    for(int t = 0; t <= N; ++t){
        for(auto [kth, id] : queries[t])
            ans[id] = get_kth(kth);
        if(demand) simulate();
    }

    for(int i = 0; i < Q; ++i){
        cout << ans[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'fenwick_tree::fenwick_tree(int)':
Main.cpp:12:22: warning: 'fenwick_tree::ar' will be initialized after [-Wreorder]
   12 |     vector<int> bit, ar;
      |                      ^~
Main.cpp:11:9: warning:   'int fenwick_tree::L' [-Wreorder]
   11 |     int L;
      |         ^
Main.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     fenwick_tree(int n) : bit(n + 1, 0), ar(n + 1, 0), L(31 - __builtin_clz(n)) {}
      |     ^~~~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:91:13: warning: unused variable 'position_head' [-Wunused-variable]
   91 |         int position_head = q[head];
      |             ^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:111:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |         for(auto [kth, id] : queries[t])
      |                  ^

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25