Submission #1111788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111788		MisterReaper	Abracadabra (CEOI22_abracadabra)	C++17	75 / 100	3067 ms	39328 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

// #undef DEBUG
#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(2E5) + 5;
constexpr int max_Q = int(1E6) + 5;
constexpr int LG = 19;

int N, Q;
int A[max_N];
int T[max_Q], I[max_Q], ans[max_Q];

int inv_p[max_N];

struct node {
    int act, siz;
} tree[max_N << 2];
node unite(const node lhs, const node rhs) {
    return {lhs.act + rhs.act, lhs.siz + rhs.siz};
}
void tree_build(int v, int l, int r) {
    if (l == r) {
        tree[v] = {0, 0};
        return;
    }
    int mid = (l + r) >> 1;
    tree_build(v << 1, l, mid);
    tree_build(v << 1 | 1, mid + 1, r);
    tree[v] = unite(tree[v << 1], tree[v << 1 | 1]);
}
void tree_build() {
    tree_build(1, 0, N);
}
void tree_add(int v, int l, int r, int x, int y) {
    if (l == r) {
        tree[v] = {1, y};
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        tree_add(v << 1, l, mid, x, y);
    } else {
        tree_add(v << 1 | 1, mid + 1, r, x, y);
    }
    tree[v] = unite(tree[v << 1], tree[v << 1 | 1]);
}
void tree_add(int x, int y) {
    tree_add(1, 0, N, x, y);
}
int tree_get_kth_act(int v, int l, int r, int k) {
    if (l == r) {
        return l;
    }
    int mid = (l + r) >> 1;
    int left_act_size = tree[v << 1].act;
    if (k < left_act_size) {
        return tree_get_kth_act(v << 1, l, mid, k);
    } else {
        return tree_get_kth_act(v << 1 | 1, mid + 1, r, k - left_act_size);
    }
}
int tree_get_kth_act(int k) {
    return tree_get_kth_act(1, 0, N, k);
}
int tree_query(int v, int l, int r, int x) {
    if (l == r) {
        return 0;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        return tree_query(v << 1, l, mid, x);
    } else {
        return tree_query(v << 1 | 1, mid + 1, r, x) + tree[v << 1].siz;
    }
}
int tree_query(int x) {
    return tree_query(1, 0, N, x);
}

void debug_tree() {
    #ifdef DEBUG
        int n = tree[1].act;
        for (int i = 0; i < n; ++i) {
            int x = tree_get_kth_act(i);
            std::cerr << x << ' ' << tree_query(x) << '\n';
        }
    #endif
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); 

    std::cin >> N >> Q;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        --A[i];
    }

    for (int i = 0; i < N; ++i) {
        inv_p[A[i]] = i;
    }
    A[N] = N;
    inv_p[N] = N;

    debug("wtf");
    std::vector<int> nxt_big(N), stk{N};
    for (int i = N - 1; i >= 0; --i) {
        while (A[i] > A[stk.back()]) {
            stk.pop_back();
        }
        nxt_big[i] = stk.back();
        stk.emplace_back(i);
    }
    debug("holyf");
    tree_build();

    debug("ok");


    auto partition = [&](int l, int r) -> std::vector<int> {
        debug(l, r);
        std::vector<int> v;
        while (l <= r) {
            v.emplace_back(l);
            l = std::min(r + 1, nxt_big[l]);
        }
        debug(v);
        v.emplace_back(r + 1);
        return v;
    };

    auto add = [&](std::vector<int> v) {
        for (int i = 0; i + 1 < v.size(); ++i) {
            debug(A[v[i]], inv_p[A[v[i + 1]]], inv_p[A[v[i]]]);
            tree_add(A[v[i]], inv_p[A[v[i + 1]]] - inv_p[A[v[i]]]);
        }
    };

    add(partition(0, N - 1));
    tree_add(N, 0);
    debug_tree();

    auto get_kth = [&](int k) -> int {
        int lo = 0, hi = tree[1].act - 1;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            int x = tree_get_kth_act(mid + 1);
            int siz = tree_query(x);
            if (k < siz) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        int x = tree_get_kth_act(lo);
        int siz = tree_query(x);
        // debug(k, x, siz);
        return A[inv_p[x] + k - siz];
    };
    auto group_kth = [&](int k) -> int {
        int lo = 0, hi = tree[1].act - 1;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            int x = tree_get_kth_act(mid + 1);
            int siz = tree_query(x);
            if (k < siz) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        int x = tree_get_kth_act(lo);
        debug("group", k, tree_query(x));
        return x;
    };

    #ifdef DEBUG
        for (int i = 0; i < N; ++i) {
            std::cerr << get_kth(i) + 1 << " \n"[i == N - 1];
        }
    #endif

    for (int i = 0; i < Q; ++i) {
        std::cin >> T[i] >> I[i];
        --I[i];
        T[i] = std::min(T[i], N);
    }

    std::vector<int> ord(Q);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return T[lhs] < T[rhs];
    });

    int curq = 0; 

    std::vector<int> a(N);
    for (int t = 0; curq < Q; ++t) {
        while (curq < Q && T[ord[curq]] == t) {
            ans[ord[curq]] = get_kth(I[ord[curq]]);
            ++curq;
        }
        int mid = get_kth(N / 2);
        int g = group_kth(N / 2);
        int size = tree_query(g + 1) - tree_query(g);
        debug(t, mid, g, size);
        if (g == mid) {
            continue;
        }
        int left_size = inv_p[mid] - inv_p[g], right_size = size - left_size;
        debug(left_size, right_size);
        auto v = partition(inv_p[mid], inv_p[mid] + right_size - 1);
        tree_add(g, inv_p[mid] - inv_p[g]);
        add(v);
        debug_tree();
        debug();
        #ifdef DEBUG
            for (int i = 0; i < N; ++i) {
                std::cerr << get_kth(i) + 1 << " \n"[i == N - 1];
            }
        #endif
    }

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

    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:141:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for (int i = 0; i + 1 < v.size(); ++i) {
      |                         ~~~~~~^~~~~~~~~~

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