Submission #646847

#	Time	Username	Problem	Language	Result	Execution time	Memory
646847		chenwz	Abracadabra (CEOI22_abracadabra)	C++11	100 / 100	784 ms	55612 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 200005;
const int MAXQ = 1000005;

int n, q, siz, ofs = 1, flg;
int p[MAXN], nxt[MAXN], sol[MAXQ];
int t[MAXN * 8];
set < pair <int, pi> > st;
vector < pair <int, pi> > v;
vector <pi> queries[MAXN];

void compute_next () {
    vector <int> st;
    st.push_back(n + 1);
    p[n + 1] = 1e9;
    for (int i = n; i >= 1; i--) {
        while (p[i] > p[st.back()]) st.pop_back();
        nxt[i] = st.back();
        st.push_back(i);
    }
}

int get_idx (int a, int b) {
    return lower_bound(v.begin(), v.end(), make_pair(p[a], make_pair(a, b))) - v.begin();
}

void tour_init () {
    sort(v.begin(), v.end());
    while (ofs < v.size()) ofs *= 2;
}

void update (int i, int tip) {
    t[i + ofs] = v[i].second.second - v[i].second.first + 1;
    if (tip == -1) t[i + ofs] = 0;
    i = (i + ofs) / 2;
    while (i > 0) {
        t[i] = t[2 * i] + t[2 * i + 1];
        i /= 2;
    }
}

int upit (int x, int val, int lo = 0, int hi = ofs - 1) {
    if (lo == hi) return p[v[lo].second.first + val - 1];
    if (val <= t[2 * x]) return upit(2 * x, val, lo, (lo + hi) / 2);
    return upit(2 * x + 1, val - t[2 * x], (lo + hi) / 2 + 1, hi);
}

void ubaci (int a, int b) {
    st.insert({p[a], {a, b}});
    siz += b - a + 1;
    if (flg == 0) v.push_back({p[a], {a, b}});
    if (flg == 1) update(get_idx(a, b), 1);
}

void podijeli (int a, int b) {
    while (a <= b) {
        int lim = min(nxt[a] - 1, b);
        ubaci(a, lim);
        a = nxt[a];
    }
}

void remove_from_back () {
    while (1) {
        int a = (st.rbegin()->second).first;
        int b = (st.rbegin()->second).second;
        if (siz - (b - a + 1) < n / 2) break;
        auto it = st.end(); it--;
        st.erase(it);
        siz -= b - a + 1;
    }
}

void update_mid () {
    int a = (st.rbegin()->second).first;
    int b = (st.rbegin()->second).second;
    st.erase({p[a], {a, b}});
    siz -= b - a + 1;
    if (flg) update(get_idx(a, b), -1);
    int ofs = n / 2 - siz;
    ubaci(a, a + ofs - 1);
    podijeli(a + ofs, b);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 1; i <= q; i++) {
        int t, pos;
        cin >> t >> pos;
        t = min(t, n);
        queries[t].push_back({i, pos});
    }
    compute_next();
    podijeli(1, n);
    while (1) {
        remove_from_back();
        if (siz == n / 2) break;
        update_mid();
    }
    tour_init();

    siz = 0; flg = 1;
    st.clear();
    podijeli(1, n);
    for (int t = 0; t <= n; t++) {
        for (auto pp : queries[t]) {
            int i = pp.first, pos = pp.second;
            sol[i] = upit(1, pos);
        }
        if (siz > n / 2) {
            remove_from_back();
            update_mid();
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << sol[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void tour_init()':
Main.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (ofs < v.size()) ofs *= 2;
      |            ~~~~^~~~~~~~~~

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