Submission #683019

#	Time	Username	Problem	Language	Result	Execution time	Memory
683019		nutella	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3085 ms	35220 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) - 1].push_back({i, p});
    }

    vector<int> save = a;
    riffle_shuffle(save);

    a = save;

    const int logn = __lg(n) + 1;

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

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

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

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

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

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

        return comp(mn[lg][l], mn[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);
        }
    }

    vector<int> b(n, -1);

    auto check = [&]() {
        int x = fn.lower_bound(n / 2);
        int sum = fn.sum(x);

        if (sum == n / 2) {
            int i = 0;
            while (fn.S > 0) {
                int y = fn.lower_bound(1);
                for (int j = segment[y].first; j < segment[y].second; ++j) {
                    b[i++] = a[j];
                }
                fn.modify(y, -(segment[y].second - segment[y].first));
            }

            return true;
        }

        return false;
    };

    auto normalize = [&]() {
        int x = fn.lower_bound(n / 2);
        int sum = fn.sum(x);

        int i = sum;
        while (fn.S != sum) {
            int y = fn.lower_bound(sum + 1);
            for (int j = segment[y].first; j < segment[y].second; ++j) {
                b[i++] = a[j];
            }
            fn.modify(y, -(segment[y].second - segment[y].first));
        }
    };

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

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

            if (rangeMin(l, mid) == l) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        return hi;
    };

    auto getValue = [&](int p) {
        if (b[p] != -1) {
            return b[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];
    };


    auto print = [&]() {
        cout << "save: ";
        for (int x: save) cout << x + 1 << " ";
        cout << '\n';
        cout << "a   : ";
        for (int i = 0; i < n; ++i) {
            cout << getValue(i) + 1 << " ";
        }
        cout << endl << endl;
    };


    normalize();

    for (auto [i, p] : queries[0]) {
        ans[i] = save[p];
    }

    for (int _ = 1; _ < n; ++_) {
        if (b[0] == -1) {
            if (!check()) {
                int x = fn.lower_bound(n / 2);

                int sum = fn.sum(x);
                int sum_l = sum - (segment[x].second - segment[x].first);
                assert(sum_l < n / 2);

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

                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;
                }

                normalize();
            }
        }

        riffle_shuffle(save);
//
//        print();

        for (auto [i, p]: queries[_]) {
            ans[i] = save[p]; //getValue(p);
        }
    }

    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:109:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  109 |             mn[l][i] = comp(mn[l - 1][i], mn[l - 1][i + (1 << l - 1)]);
      |                                                               ~~^~~
Main.cpp:223:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
  223 |     auto print = [&]() {
      |          ^~~~~

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