oj.uz

Submission #1111786

# Submission time Handle Problem Language Result Execution time Memory
1111786 2024-11-12T22:45:34 Z MisterReaper Abracadabra (CEOI22_abracadabra) C++17
75 / 100
 3000 ms 75264 KB 
#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];

std::pair<int, int> st[LG][max_N];
void build_st() {
    for (int i = 0; i < N; ++i) {
        st[0][i] = {A[i], i};
    }
    for (int lg = 0; lg < LG; ++lg) {
        for (int i = 0; i + (1 << lg) < N; ++i) {
            st[lg + 1][i] = std::max(st[lg][i], st[lg][i + (1 << lg)]);
        }
    }
}
std::pair<int, int> get_st(int l, int r) {
    int d = (r - l + 1);
    int lg = std::__lg(d);
    return std::max(st[lg][l], st[lg][r - (1 << lg) + 1]);
}

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");
    build_st();
    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);
            int lo = l, hi = r;
            while (lo < hi) {
                int mid = (lo + hi + 1) >> 1;
                if (A[l] >= get_st(l, mid).first) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
            l = lo + 1;
        }
        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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 47852 KB Output is correct
2 Correct 670 ms 47436 KB Output is correct
3 Correct 606 ms 46920 KB Output is correct
4 Correct 308 ms 45696 KB Output is correct
5 Correct 451 ms 47176 KB Output is correct
6 Correct 421 ms 45896 KB Output is correct
7 Correct 524 ms 47432 KB Output is correct
8 Correct 422 ms 46048 KB Output is correct
9 Correct 445 ms 45896 KB Output is correct
10 Correct 437 ms 46108 KB Output is correct
11 Correct 393 ms 46088 KB Output is correct
12 Correct 342 ms 45180 KB Output is correct
13 Correct 381 ms 45964 KB Output is correct
14 Correct 433 ms 46664 KB Output is correct
15 Correct 390 ms 46504 KB Output is correct
16 Correct 3 ms 24912 KB Output is correct
17 Correct 509 ms 45452 KB Output is correct
18 Correct 207 ms 45128 KB Output is correct
19 Correct 2 ms 10576 KB Output is correct
20 Correct 2 ms 10576 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 75264 KB Output is correct
2 Correct 1204 ms 74100 KB Output is correct
3 Correct 1022 ms 68336 KB Output is correct
4 Correct 832 ms 68320 KB Output is correct
5 Correct 887 ms 68976 KB Output is correct
6 Correct 754 ms 68004 KB Output is correct
7 Correct 965 ms 74172 KB Output is correct
8 Correct 979 ms 72948 KB Output is correct
9 Correct 909 ms 68716 KB Output is correct
10 Correct 840 ms 71684 KB Output is correct
11 Correct 593 ms 67144 KB Output is correct
12 Correct 731 ms 67144 KB Output is correct
13 Correct 843 ms 71172 KB Output is correct
14 Correct 631 ms 67912 KB Output is correct
15 Correct 742 ms 72520 KB Output is correct
16 Correct 22 ms 44368 KB Output is correct
17 Correct 1043 ms 69280 KB Output is correct
18 Correct 282 ms 65060 KB Output is correct
19 Correct 97 ms 54124 KB Output is correct
20 Correct 410 ms 55624 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 45008 KB Output is correct
2 Correct 462 ms 45008 KB Output is correct
3 Correct 497 ms 45108 KB Output is correct
4 Correct 217 ms 44872 KB Output is correct
5 Correct 307 ms 45128 KB Output is correct
6 Correct 227 ms 44832 KB Output is correct
7 Correct 271 ms 44920 KB Output is correct
8 Correct 269 ms 44968 KB Output is correct
9 Correct 315 ms 44872 KB Output is correct
10 Correct 188 ms 44872 KB Output is correct
11 Correct 213 ms 44872 KB Output is correct
12 Correct 174 ms 44616 KB Output is correct
13 Correct 241 ms 44872 KB Output is correct
14 Correct 206 ms 44872 KB Output is correct
15 Correct 160 ms 44616 KB Output is correct
16 Correct 15 ms 40784 KB Output is correct
17 Correct 311 ms 44608 KB Output is correct
18 Correct 63 ms 44616 KB Output is correct
19 Correct 2 ms 10576 KB Output is correct
20 Correct 2 ms 10576 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 47852 KB Output is correct
2 Correct 670 ms 47436 KB Output is correct
3 Correct 606 ms 46920 KB Output is correct
4 Correct 308 ms 45696 KB Output is correct
5 Correct 451 ms 47176 KB Output is correct
6 Correct 421 ms 45896 KB Output is correct
7 Correct 524 ms 47432 KB Output is correct
8 Correct 422 ms 46048 KB Output is correct
9 Correct 445 ms 45896 KB Output is correct
10 Correct 437 ms 46108 KB Output is correct
11 Correct 393 ms 46088 KB Output is correct
12 Correct 342 ms 45180 KB Output is correct
13 Correct 381 ms 45964 KB Output is correct
14 Correct 433 ms 46664 KB Output is correct
15 Correct 390 ms 46504 KB Output is correct
16 Correct 3 ms 24912 KB Output is correct
17 Correct 509 ms 45452 KB Output is correct
18 Correct 207 ms 45128 KB Output is correct
19 Correct 2 ms 10576 KB Output is correct
20 Correct 2 ms 10576 KB Output is correct
21 Correct 1566 ms 75264 KB Output is correct
22 Correct 1204 ms 74100 KB Output is correct
23 Correct 1022 ms 68336 KB Output is correct
24 Correct 832 ms 68320 KB Output is correct
25 Correct 887 ms 68976 KB Output is correct
26 Correct 754 ms 68004 KB Output is correct
27 Correct 965 ms 74172 KB Output is correct
28 Correct 979 ms 72948 KB Output is correct
29 Correct 909 ms 68716 KB Output is correct
30 Correct 840 ms 71684 KB Output is correct
31 Correct 593 ms 67144 KB Output is correct
32 Correct 731 ms 67144 KB Output is correct
33 Correct 843 ms 71172 KB Output is correct
34 Correct 631 ms 67912 KB Output is correct
35 Correct 742 ms 72520 KB Output is correct
36 Correct 22 ms 44368 KB Output is correct
37 Correct 1043 ms 69280 KB Output is correct
38 Correct 282 ms 65060 KB Output is correct
39 Correct 97 ms 54124 KB Output is correct
40 Correct 410 ms 55624 KB Output is correct
41 Correct 528 ms 45008 KB Output is correct
42 Correct 462 ms 45008 KB Output is correct
43 Correct 497 ms 45108 KB Output is correct
44 Correct 217 ms 44872 KB Output is correct
45 Correct 307 ms 45128 KB Output is correct
46 Correct 227 ms 44832 KB Output is correct
47 Correct 271 ms 44920 KB Output is correct
48 Correct 269 ms 44968 KB Output is correct
49 Correct 315 ms 44872 KB Output is correct
50 Correct 188 ms 44872 KB Output is correct
51 Correct 213 ms 44872 KB Output is correct
52 Correct 174 ms 44616 KB Output is correct
53 Correct 241 ms 44872 KB Output is correct
54 Correct 206 ms 44872 KB Output is correct
55 Correct 160 ms 44616 KB Output is correct
56 Correct 15 ms 40784 KB Output is correct
57 Correct 311 ms 44608 KB Output is correct
58 Correct 63 ms 44616 KB Output is correct
59 Correct 2 ms 10576 KB Output is correct
60 Correct 2 ms 10576 KB Output is correct
61 Correct 2972 ms 74744 KB Output is correct
62 Execution timed out 3037 ms 67700 KB Time limit exceeded
63 Halted 0 ms 0 KB -