oj.uz

Submission #724076

# Submission time Handle Problem Language Result Execution time Memory
724076 2023-04-14T16:56:24 Z bitaro1337 Abracadabra (CEOI22_abracadabra) C++14
25 / 100
 982 ms 103212 KB 
//BITARO BITARO BITARO
#include <bits/stdc++.h>
using namespace std;

const int N = 8e5 + 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

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 982 ms 103212 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 239 ms 30972 KB Output is correct
2 Correct 212 ms 30976 KB Output is correct
3 Correct 239 ms 29608 KB Output is correct
4 Correct 128 ms 24712 KB Output is correct
5 Correct 208 ms 28532 KB Output is correct
6 Correct 135 ms 25072 KB Output is correct
7 Correct 186 ms 27052 KB Output is correct
8 Correct 150 ms 26000 KB Output is correct
9 Correct 174 ms 27172 KB Output is correct
10 Correct 109 ms 23628 KB Output is correct
11 Correct 113 ms 23992 KB Output is correct
12 Correct 104 ms 23628 KB Output is correct
13 Correct 113 ms 23756 KB Output is correct
14 Correct 111 ms 23808 KB Output is correct
15 Correct 112 ms 23496 KB Output is correct
16 Correct 52 ms 20664 KB Output is correct
17 Correct 182 ms 30836 KB Output is correct
18 Correct 91 ms 22996 KB Output is correct
19 Correct 10 ms 19092 KB Output is correct
20 Correct 11 ms 19048 KB Output is correct

Subtask #4
0 / 25.0

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