oj.uz

Submission #683019

# Submission time Handle Problem Language Result Execution time Memory
683019 2023-01-17T14:26:26 Z nutella Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 35220 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18304 KB Output is correct
2 Correct 201 ms 17868 KB Output is correct
3 Correct 193 ms 17512 KB Output is correct
4 Correct 183 ms 16312 KB Output is correct
5 Correct 197 ms 19540 KB Output is correct
6 Correct 195 ms 20204 KB Output is correct
7 Correct 205 ms 20716 KB Output is correct
8 Correct 187 ms 18492 KB Output is correct
9 Correct 188 ms 17332 KB Output is correct
10 Correct 195 ms 17312 KB Output is correct
11 Correct 197 ms 17612 KB Output is correct
12 Correct 183 ms 14652 KB Output is correct
13 Correct 222 ms 16380 KB Output is correct
14 Correct 187 ms 19000 KB Output is correct
15 Correct 200 ms 16480 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 165 ms 8776 KB Output is correct
18 Correct 178 ms 12436 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 320 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 35220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 14556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18304 KB Output is correct
2 Correct 201 ms 17868 KB Output is correct
3 Correct 193 ms 17512 KB Output is correct
4 Correct 183 ms 16312 KB Output is correct
5 Correct 197 ms 19540 KB Output is correct
6 Correct 195 ms 20204 KB Output is correct
7 Correct 205 ms 20716 KB Output is correct
8 Correct 187 ms 18492 KB Output is correct
9 Correct 188 ms 17332 KB Output is correct
10 Correct 195 ms 17312 KB Output is correct
11 Correct 197 ms 17612 KB Output is correct
12 Correct 183 ms 14652 KB Output is correct
13 Correct 222 ms 16380 KB Output is correct
14 Correct 187 ms 19000 KB Output is correct
15 Correct 200 ms 16480 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 165 ms 8776 KB Output is correct
18 Correct 178 ms 12436 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Execution timed out 3080 ms 35220 KB Time limit exceeded
22 Halted 0 ms 0 KB -