Submission #724078

#	Time	Username	Problem	Language	Result	Execution time	Memory
724078		bitaro1337	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	1569 ms	100116 KiB

Main

//BITARO BITARO BITARO
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 5;
int ans[N], a[N], nxt[N], fen[N], total_len, ttp;
vector<array<int, 3>> values;
vector<pair<int, int>> queries[N];
set<array<int, 3>> s;
int n, q;

void modif(int u, int val) {
    for(int i = u + 1; i < N; i += i & -i) fen[i] += val;
}
int query(int u) {
    int ret = 0;
    for(int i = u + 1; i >= 1; i -= i & -i) ret += fen[i];
    return ret;
}

int id(array<int, 3> x) {
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}
void fix() {
    while(true) {
        int A = (*s.rbegin())[1], B = (*s.rbegin())[2];
        if(total_len - (B - A + 1) >= n / 2) {
            s.erase(--s.end());
            total_len -= B - A + 1;
        }
        else break;
    }
}
void add(int x, int y) {
    s.insert({a[x], x, y});
    total_len += y - x + 1;
    if(!ttp) values.push_back({a[x], x, y});
    else modif(id({a[x], x, y}), y - x + 1);
}
void go(int l, int r) {
    for(int i = l; i <= r; i = nxt[i]) {
        add(i, min(nxt[i] - 1, r));
    }
}
void remove_middle() {
    if(total_len == n / 2) return;
    array<int, 3> x = *--s.end();
    s.erase(--s.end());
    if(ttp) modif(id(x), -(x[2] - x[1] + 1));
    int l = x[1], r = x[2];
    total_len -= r - l + 1;
    int need_add = n / 2 - total_len;
    add(l, l + need_add - 1);
    go(l + need_add, r);
}

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1, t, pos; i <= q; ++i) {
        cin >> t >> pos; t = min(t, n);
        queries[t].push_back(make_pair(i, pos));
    }
    stack<int> st;
    for(int i = n; i >= 1; --i) {
        while(!st.empty() && a[st.top()] < a[i]) st.pop();
        nxt[i] = (st.empty() ? n + 1 : st.top());
        st.push(i);
    }
    go(1, n);
    while(true) {
        fix();
        if(total_len == n / 2) break;
        remove_middle();
    }
    s.clear(); ttp = 1; total_len = 0;
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    go(1, n);
    for(int t = 0; t <= n; ++t) {
        for(auto x: queries[t]) {
            int pos = x.second, idx = x.first;
            int f = -1, l = 0, r = N - 1;
            while(l <= r) {
                int mid = l + r >> 1;
                if(query(mid) < pos) {
                    l = mid + 1;
                    f = mid;
                } else {
                    r = mid - 1;
                }
            }
            if(f >= 0) pos -= query(f);
            ++f;
            ans[idx] = a[values[f][1] + pos - 1];
        }
        if(total_len > n / 2) {
            fix();
            remove_middle();
        }
    }
    for(int i = 1; i <= q; ++i) {
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:85:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |                 int mid = l + r >> 1;
      |                           ~~^~~

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