Submission #683100

#	Time	Username	Problem	Language	Result	Execution time	Memory
683100		nutella	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	715 ms	56036 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void riffle_shuffle(vector<int> &a) {
    vector<int> L(a.begin(), a.begin() + a.size() / 2);
    vector<int> R(a.begin() + a.size() / 2, a.end());

    int i = 0, j = 0;
    int n = a.size() / 2;

    while (i < n || j < n) {
        if (i != n && (j == n || L[i] < R[j])) {
            a[j + i] = L[i];
            i += 1;
        } else {
            a[j + i] = R[j];
            j += 1;
        }
    }
}

struct Fenwick {
    vector<int> t;
    int n, S = 0;

    Fenwick() = default;

    Fenwick(int n) : n(n), t(n + 1) {}

    void modify(int i, int v) {
        S += v;
        for (int x = i + 1; x <= n; x += x & -x) {
            t[x] += v;
        }
    }

    int sum(int i) {
        int ans = 0;
        for (int x = i + 1; x > 0; x -= x & -x) {
            ans += t[x];
        }
        return ans;
    }

    int lower_bound(int k) {
        int x = 0;
        for (int i = 1 << __lg(n); i > 0; i >>= 1) {
            if (x + i <= n && t[x + i] < k) {
                x += i;
                k -= t[x];
            }
        }
        return x;
    }
};

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

    int n, q;
    cin >> n >> q;


    vector<int> a(n);

    for (int &x: a) {
        cin >> x;
        x -= 1;
    }

    vector<int> ans(q, -1);

    vector<vector<array<int, 2>>> queries(n + 1);

    for (int i = 0; i < q; ++i) {
        int t, p;
        cin >> t >> p;

        p -= 1;

        if (t == 0) {
            ans[i] = a[p];
            continue;
        }

        queries[min(t, n)].push_back({i, p});
    }

    const int logn = __lg(n) + 1;

    auto comp = [&](int i, int j) {
        return a[i] > a[j] ? i : j;
    };

    vector<vector<int>> mx(logn);

    mx[0].resize(n);
    iota(mx[0].begin(), mx[0].end(), 0);

    for (int l = 1; l < logn; ++l) {
        mx[l].resize(n - (1 << l) + 1);

        for (int i = 0; i + (1 << l) <= n; ++i) {
            mx[l][i] = comp(mx[l - 1][i], mx[l - 1][i + (1 << l - 1)]);
        }
    }

    auto rangeMax = [&](int l, int r) {
        int lg = __lg(r - l);

        return comp(mx[lg][l], mx[lg][r - (1 << lg)]);
    };

    Fenwick fn(n);

    vector<pair<int, int>> segment(n, {-1, -1});

    int pref_mx = -1;
    for (int i = 0; i < n / 2; ++i) {
        if (pref_mx < a[i]) {
            if (pref_mx != -1) {
                segment[pref_mx].second = i;
            }
            pref_mx = a[i];
            segment[pref_mx].first = i;
        }
    }
    segment[pref_mx].second = n / 2;

    pref_mx = -1;
    for (int i = n / 2; i < n; ++i) {
        if (pref_mx < a[i]) {
            if (pref_mx != -1) {
                segment[pref_mx].second = i;
            }
            pref_mx = a[i];
            segment[pref_mx].first = i;
        }
    }
    segment[pref_mx].second = n;

    for (int x = 0; x < n; ++x) {
        if (segment[x].first != -1) {
            fn.modify(x, segment[x].second - segment[x].first);
        }
    }

    auto find_next = [&](int l, int r) {
        int mx = rangeMax(l, r);
        if (l == mx) {
            return -1;
        }

        int lo = l, hi = r;
        while (lo + 1 < hi) {
            int mid = (lo + hi) >> 1;

            if (rangeMax(l, mid + 1) == l) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        return hi;
    };

    auto getValue = [&](int p) {
        p += 1;

        int x = fn.lower_bound(p);
        int sum_l = fn.sum(x - 1);

        return a[segment[x].first + (p - sum_l) - 1];
    };

    for (int _ = 1; _ <= n; ++_) {
        for (auto [i, p]: queries[_]) {
            ans[i] = getValue(p);
        }

        int x = fn.lower_bound(n / 2);

        int sum = fn.sum(x);
        
        if (sum == n / 2) {
            continue;
        }
        
        int sum_l = sum - (segment[x].second - segment[x].first);

        int cut = segment[x].first + (n / 2 - sum_l);

        fn.modify(x, cut - segment[x].second);


        int l = cut, r = segment[x].second;

        segment[x].second = cut;

        while (l < r) {
            int mid = find_next(l, r);

            if (mid == -1) {
                segment[a[l]].first = l, segment[a[l]].second = r;
            } else {
                segment[a[l]].first = l, segment[a[l]].second = mid;
            }

            fn.modify(a[l], segment[a[l]].second - segment[a[l]].first);

            l = segment[a[l]].second;
        }

    }

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

    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'Fenwick::Fenwick(int)':
Main.cpp:25:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
   25 |     int n, S = 0;
      |         ^
Main.cpp:24:17: warning:   'std::vector<int> Fenwick::t' [-Wreorder]
   24 |     vector<int> t;
      |                 ^
Main.cpp:29:5: warning:   when initialized here [-Wreorder]
   29 |     Fenwick(int n) : n(n), t(n + 1) {}
      |     ^~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:106:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  106 |             mx[l][i] = comp(mx[l - 1][i], mx[l - 1][i + (1 << l - 1)]);
      |                                                               ~~^~~

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