Submission #683043

#	Time	Username	Problem	Language	Result	Execution time	Memory
683043		nutella	Abracadabra (CEOI22_abracadabra)	C++17	65 / 100	3079 ms	40228 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;
    }
};

#define STRESS 0

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

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


    vector<int> a(n);
    if (!STRESS) {
        for (int &x: a) {
            cin >> x;
            x -= 1;
        }
    } else {
        iota(a.begin(), a.end(), 0);
        mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
        shuffle(a.begin(), a.end(), rnd);
    }

//    cerr << "initial: ";
//    for (int x : a) cerr << x + 1 << " ";
//    cerr << endl;

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

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

    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);
        
        assert(fn.S == fn.sum(n - 1));
        
        int i = sum;
        while (fn.S != sum) {
//            assert(fn.S > sum);
            int y = fn.lower_bound(sum + 1);
//            assert(y > x);
            for (int j = segment[y].first; j < segment[y].second; ++j) {
                assert(b[i] == -1);
                b[i++] = a[j];
            }
            fn.modify(y, -(segment[y].second - segment[y].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) {
        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 = [&]() {
//        cerr << "save: ";
//        for (int x: save) cerr << x + 1 << " ";
//        cerr << '\n';
//        cerr << "a   : ";
//        for (int i = 0; i < n; ++i) {
//            cerr << getValue(i) + 1 << " ";
//        }
//        cerr << endl << endl;
//        for (int i = 0; i < n; ++i) {
//            assert(getValue(i) == save[i]);
//        }
//    };


    normalize();

    for (int _ = 1; _ <= n; ++_) {
        normalize();
        check();

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

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

        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, 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);

                    assert(l != segment[a[l]].second);
                    l = segment[a[l]].second;
                }

                normalize();
            }
        }
    }

    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:122:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  122 |             mx[l][i] = comp(mx[l - 1][i], mx[l - 1][i + (1 << l - 1)]);
      |                                                               ~~^~~

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