oj.uz

Submission #1086908

# Submission time Handle Problem Language Result Execution time Memory
1086908 2024-09-11T16:55:45 Z alexdumitru Abracadabra (CEOI22_abracadabra) C++14
100 / 100
 746 ms 73136 KB 
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

const int NMAX = 2e5 + 5;
const int QMAX = 1e6 + 5;

int n, q;
int a[NMAX + 2];
pair<int, int> qr[QMAX + 1];
int ans[QMAX + 1];
vector<int> idQ[NMAX + 1];
int nxt[NMAX + 2];

void read() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[n + 1] = n + 1;
    for (int i = 1; i <= q; i++) {
        cin >> qr[i].first >> qr[i].second;
        qr[i].first = min(qr[i].first, n);
        idQ[qr[i].first].push_back(i);
    }
}

struct Block {
    int v, l, r;
    bool operator < (const Block & oth) const {
        return v < oth.v;
    }
};

set<Block> s;
vector<Block> vtot;
map<Block, int> mp;

namespace AIB {
    int aib[2 * NMAX + 1];
    int m;

    int query(int pos) {
        int res = 0;
        for (; pos > 0; pos -= pos & -pos)
            res += aib[pos];
        return res;
    }

    void update(int pos, int v) {
        for (; pos <= m; pos += pos & -pos)
            aib[pos] += v;
    }

    int get_block(int pos) {
        int idx = 0, s = 0;
        for (int b = 18; b >= 0; b--) {
            if (idx + (1 << b) <= m && s + aib[idx + (1 << b)] < pos) {
                s += aib[idx + (1 << b)];
                idx += (1 << b);
            }
        }
        return idx + 1;
    }

    void init(int _m) {
        m = _m;
    }
}

void adauga(Block b) {
    s.insert(b);
    AIB::update(mp[b], + (b.r - b.l + 1));
}

void scoate(Block b) {
    s.erase(b);
    AIB::update(mp[b], - (b.r - b.l + 1));
}

void solve() {
    stack<int> stk;
    stk.push(n + 1);
    for (int i = n; i >= 1; i--) {
        while (a[stk.top()] < a[i]) stk.pop();
        nxt[i] = stk.top();
        stk.push(i);
    }

    for (int st = 1; st <= n; st = nxt[st]) {
        s.insert({a[st], st, nxt[st] - 1});
        vtot.push_back({a[st], st, nxt[st] - 1});
    }

    int ltotal = n;

    for (int step = 0; step <= n; step++) {
        while (true) {
            auto it = prev(s.end());
            if (ltotal - (it->r - it->l) > n / 2) {
                ltotal -= (it->r - it->l + 1);
                s.erase(it);
            } else break;
        }

        if (ltotal > n / 2) {
            auto ult = prev(s.end());
            int L = ult->l, R = ult->r, V = ult->v;
            s.erase(ult);

            int lgR = ltotal - n / 2;
            int lgL = R - L + 1 - lgR;

            int v1 = V;
            int l1 = L;
            int r1 = L + lgL - 1;
            s.insert({v1, l1, r1});
            vtot.push_back({v1, l1, r1});

            for (int idx = r1 + 1; idx <= R; idx = nxt[idx]) {
                s.insert({a[idx], idx, min(idx + lgR - 1, nxt[idx] - 1)});
                vtot.push_back({a[idx], idx, min(idx + lgR - 1, nxt[idx] - 1)});
                int ceva = min(idx + lgR - 1, nxt[idx] - 1) - idx + 1;
                lgR -= ceva;
            }
        }
    }

    sort(vtot.begin(), vtot.end());

    int cnt = vtot.size();

    for (int i = 0; i < cnt; i++) {
        mp[vtot[i]] = i + 1;
    }

    s.clear();
    ltotal = n;

    AIB::init(cnt);

    for (int st = 1; st <= n; st = nxt[st]) {
        adauga({a[st], st, nxt[st] - 1});
    }

    ltotal = n;

    for (int step = 0; step <= n; step++) {
        for (int idxQ : idQ[step]) {
            int pos = qr[idxQ].second;
            int t = AIB::get_block(pos);
            ans[idxQ] = a[vtot[t - 1].l + pos - AIB::query(t - 1) - 1];
        }

        while (true) {
            auto it = prev(s.end());
            if (ltotal - (it->r - it->l) > n / 2) {
                ltotal -= (it->r - it->l + 1);
                s.erase(*it);
            } else break;
        }

        if (ltotal > n / 2) {
            auto ult = prev(s.end());
            int L = ult->l, R = ult->r, V = ult->v;
            scoate(*ult);

            int lgR = ltotal - n / 2;
            int lgL = R - L + 1 - lgR;

            int v1 = V;
            int l1 = L;
            int r1 = L + lgL - 1;
            adauga({v1, l1, r1});

            for (int idx = r1 + 1; idx <= R; idx = nxt[idx]) {
                adauga({a[idx], idx, min(idx + lgR - 1, nxt[idx] - 1)});
                int ceva = min(idx + lgR - 1, nxt[idx] - 1) - idx + 1;
                lgR -= ceva;
            }
        }
    }
}

void write() {
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

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

    read();
    solve();
    write();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 33876 KB Output is correct
2 Correct 214 ms 32496 KB Output is correct
3 Correct 192 ms 31828 KB Output is correct
4 Correct 163 ms 30972 KB Output is correct
5 Correct 185 ms 33312 KB Output is correct
6 Correct 170 ms 32592 KB Output is correct
7 Correct 184 ms 34132 KB Output is correct
8 Correct 166 ms 31824 KB Output is correct
9 Correct 161 ms 31576 KB Output is correct
10 Correct 169 ms 31172 KB Output is correct
11 Correct 180 ms 31060 KB Output is correct
12 Correct 157 ms 29392 KB Output is correct
13 Correct 164 ms 30916 KB Output is correct
14 Correct 174 ms 32396 KB Output is correct
15 Correct 180 ms 31740 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 168 ms 29708 KB Output is correct
18 Correct 153 ms 29620 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 5188 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 68000 KB Output is correct
2 Correct 387 ms 68544 KB Output is correct
3 Correct 436 ms 57572 KB Output is correct
4 Correct 240 ms 42432 KB Output is correct
5 Correct 271 ms 43712 KB Output is correct
6 Correct 251 ms 41964 KB Output is correct
7 Correct 245 ms 45824 KB Output is correct
8 Correct 255 ms 46272 KB Output is correct
9 Correct 246 ms 41664 KB Output is correct
10 Correct 212 ms 40552 KB Output is correct
11 Correct 160 ms 33724 KB Output is correct
12 Correct 200 ms 34944 KB Output is correct
13 Correct 207 ms 39360 KB Output is correct
14 Correct 197 ms 35264 KB Output is correct
15 Correct 221 ms 41292 KB Output is correct
16 Correct 18 ms 8024 KB Output is correct
17 Correct 353 ms 64708 KB Output is correct
18 Correct 148 ms 31424 KB Output is correct
19 Correct 53 ms 14028 KB Output is correct
20 Correct 63 ms 15824 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 23728 KB Output is correct
2 Correct 123 ms 23552 KB Output is correct
3 Correct 160 ms 22016 KB Output is correct
4 Correct 47 ms 11664 KB Output is correct
5 Correct 108 ms 17492 KB Output is correct
6 Correct 55 ms 12176 KB Output is correct
7 Correct 89 ms 15116 KB Output is correct
8 Correct 66 ms 13576 KB Output is correct
9 Correct 90 ms 15620 KB Output is correct
10 Correct 33 ms 10064 KB Output is correct
11 Correct 38 ms 10320 KB Output is correct
12 Correct 32 ms 9772 KB Output is correct
13 Correct 36 ms 10320 KB Output is correct
14 Correct 34 ms 10076 KB Output is correct
15 Correct 31 ms 9572 KB Output is correct
16 Correct 11 ms 6756 KB Output is correct
17 Correct 101 ms 23140 KB Output is correct
18 Correct 25 ms 9300 KB Output is correct
19 Correct 3 ms 4952 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 33876 KB Output is correct
2 Correct 214 ms 32496 KB Output is correct
3 Correct 192 ms 31828 KB Output is correct
4 Correct 163 ms 30972 KB Output is correct
5 Correct 185 ms 33312 KB Output is correct
6 Correct 170 ms 32592 KB Output is correct
7 Correct 184 ms 34132 KB Output is correct
8 Correct 166 ms 31824 KB Output is correct
9 Correct 161 ms 31576 KB Output is correct
10 Correct 169 ms 31172 KB Output is correct
11 Correct 180 ms 31060 KB Output is correct
12 Correct 157 ms 29392 KB Output is correct
13 Correct 164 ms 30916 KB Output is correct
14 Correct 174 ms 32396 KB Output is correct
15 Correct 180 ms 31740 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 168 ms 29708 KB Output is correct
18 Correct 153 ms 29620 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 5188 KB Output is correct
21 Correct 490 ms 68000 KB Output is correct
22 Correct 387 ms 68544 KB Output is correct
23 Correct 436 ms 57572 KB Output is correct
24 Correct 240 ms 42432 KB Output is correct
25 Correct 271 ms 43712 KB Output is correct
26 Correct 251 ms 41964 KB Output is correct
27 Correct 245 ms 45824 KB Output is correct
28 Correct 255 ms 46272 KB Output is correct
29 Correct 246 ms 41664 KB Output is correct
30 Correct 212 ms 40552 KB Output is correct
31 Correct 160 ms 33724 KB Output is correct
32 Correct 200 ms 34944 KB Output is correct
33 Correct 207 ms 39360 KB Output is correct
34 Correct 197 ms 35264 KB Output is correct
35 Correct 221 ms 41292 KB Output is correct
36 Correct 18 ms 8024 KB Output is correct
37 Correct 353 ms 64708 KB Output is correct
38 Correct 148 ms 31424 KB Output is correct
39 Correct 53 ms 14028 KB Output is correct
40 Correct 63 ms 15824 KB Output is correct
41 Correct 155 ms 23728 KB Output is correct
42 Correct 123 ms 23552 KB Output is correct
43 Correct 160 ms 22016 KB Output is correct
44 Correct 47 ms 11664 KB Output is correct
45 Correct 108 ms 17492 KB Output is correct
46 Correct 55 ms 12176 KB Output is correct
47 Correct 89 ms 15116 KB Output is correct
48 Correct 66 ms 13576 KB Output is correct
49 Correct 90 ms 15620 KB Output is correct
50 Correct 33 ms 10064 KB Output is correct
51 Correct 38 ms 10320 KB Output is correct
52 Correct 32 ms 9772 KB Output is correct
53 Correct 36 ms 10320 KB Output is correct
54 Correct 34 ms 10076 KB Output is correct
55 Correct 31 ms 9572 KB Output is correct
56 Correct 11 ms 6756 KB Output is correct
57 Correct 101 ms 23140 KB Output is correct
58 Correct 25 ms 9300 KB Output is correct
59 Correct 3 ms 4952 KB Output is correct
60 Correct 2 ms 4956 KB Output is correct
61 Correct 746 ms 73136 KB Output is correct
62 Correct 626 ms 71104 KB Output is correct
63 Correct 731 ms 67520 KB Output is correct
64 Correct 467 ms 50872 KB Output is correct
65 Correct 472 ms 53328 KB Output is correct
66 Correct 417 ms 50880 KB Output is correct
67 Correct 345 ms 47044 KB Output is correct
68 Correct 357 ms 47304 KB Output is correct
69 Correct 384 ms 49440 KB Output is correct
70 Correct 294 ms 42028 KB Output is correct
71 Correct 241 ms 41812 KB Output is correct
72 Correct 290 ms 42056 KB Output is correct
73 Correct 270 ms 41616 KB Output is correct
74 Correct 290 ms 43288 KB Output is correct
75 Correct 281 ms 42580 KB Output is correct
76 Correct 19 ms 8024 KB Output is correct
77 Correct 485 ms 64960 KB Output is correct
78 Correct 195 ms 37044 KB Output is correct
79 Correct 2 ms 4952 KB Output is correct
80 Correct 2 ms 4956 KB Output is correct