oj.uz

답안 #683054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683054 2023-01-17T15:25:22 Z nutella Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 631 ms 61172 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;
    }
};

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

        int i = sum;
        while (fn.S > sum) {
//            assert(fn.S > sum);
            int y = fn.lower_bound(sum + 1);
//            assert(fn.lower_bound(sum + 1) > x);
//            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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 18404 KB Output is correct
2 Correct 233 ms 20212 KB Output is correct
3 Correct 246 ms 19736 KB Output is correct
4 Correct 195 ms 18500 KB Output is correct
5 Correct 215 ms 21808 KB Output is correct
6 Correct 200 ms 22412 KB Output is correct
7 Correct 218 ms 23068 KB Output is correct
8 Correct 213 ms 20860 KB Output is correct
9 Correct 197 ms 19716 KB Output is correct
10 Correct 205 ms 19568 KB Output is correct
11 Correct 212 ms 20004 KB Output is correct
12 Correct 190 ms 17016 KB Output is correct
13 Correct 198 ms 18704 KB Output is correct
14 Correct 208 ms 21332 KB Output is correct
15 Correct 204 ms 18748 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 168 ms 11084 KB Output is correct
18 Correct 178 ms 14516 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 40128 KB Output is correct
2 Correct 311 ms 40184 KB Output is correct
3 Correct 300 ms 35456 KB Output is correct
4 Correct 252 ms 35772 KB Output is correct
5 Correct 251 ms 36484 KB Output is correct
6 Correct 241 ms 35092 KB Output is correct
7 Correct 296 ms 39960 KB Output is correct
8 Correct 293 ms 38232 KB Output is correct
9 Correct 272 ms 36380 KB Output is correct
10 Correct 283 ms 38108 KB Output is correct
11 Correct 222 ms 36072 KB Output is correct
12 Correct 230 ms 34944 KB Output is correct
13 Correct 270 ms 38432 KB Output is correct
14 Correct 239 ms 36060 KB Output is correct
15 Correct 274 ms 39124 KB Output is correct
16 Correct 38 ms 21796 KB Output is correct
17 Correct 225 ms 31060 KB Output is correct
18 Correct 194 ms 35248 KB Output is correct
19 Correct 75 ms 23636 KB Output is correct
20 Correct 96 ms 24340 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 13772 KB Output is correct
2 Correct 63 ms 13260 KB Output is correct
3 Correct 78 ms 13040 KB Output is correct
4 Correct 50 ms 12844 KB Output is correct
5 Correct 74 ms 13360 KB Output is correct
6 Correct 53 ms 12708 KB Output is correct
7 Correct 77 ms 13348 KB Output is correct
8 Correct 54 ms 12628 KB Output is correct
9 Correct 61 ms 13212 KB Output is correct
10 Correct 44 ms 12344 KB Output is correct
11 Correct 46 ms 12924 KB Output is correct
12 Correct 43 ms 12560 KB Output is correct
13 Correct 47 ms 12352 KB Output is correct
14 Correct 44 ms 12928 KB Output is correct
15 Correct 44 ms 12656 KB Output is correct
16 Correct 17 ms 10580 KB Output is correct
17 Correct 43 ms 11340 KB Output is correct
18 Correct 39 ms 11748 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 18404 KB Output is correct
2 Correct 233 ms 20212 KB Output is correct
3 Correct 246 ms 19736 KB Output is correct
4 Correct 195 ms 18500 KB Output is correct
5 Correct 215 ms 21808 KB Output is correct
6 Correct 200 ms 22412 KB Output is correct
7 Correct 218 ms 23068 KB Output is correct
8 Correct 213 ms 20860 KB Output is correct
9 Correct 197 ms 19716 KB Output is correct
10 Correct 205 ms 19568 KB Output is correct
11 Correct 212 ms 20004 KB Output is correct
12 Correct 190 ms 17016 KB Output is correct
13 Correct 198 ms 18704 KB Output is correct
14 Correct 208 ms 21332 KB Output is correct
15 Correct 204 ms 18748 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 168 ms 11084 KB Output is correct
18 Correct 178 ms 14516 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 341 ms 40128 KB Output is correct
22 Correct 311 ms 40184 KB Output is correct
23 Correct 300 ms 35456 KB Output is correct
24 Correct 252 ms 35772 KB Output is correct
25 Correct 251 ms 36484 KB Output is correct
26 Correct 241 ms 35092 KB Output is correct
27 Correct 296 ms 39960 KB Output is correct
28 Correct 293 ms 38232 KB Output is correct
29 Correct 272 ms 36380 KB Output is correct
30 Correct 283 ms 38108 KB Output is correct
31 Correct 222 ms 36072 KB Output is correct
32 Correct 230 ms 34944 KB Output is correct
33 Correct 270 ms 38432 KB Output is correct
34 Correct 239 ms 36060 KB Output is correct
35 Correct 274 ms 39124 KB Output is correct
36 Correct 38 ms 21796 KB Output is correct
37 Correct 225 ms 31060 KB Output is correct
38 Correct 194 ms 35248 KB Output is correct
39 Correct 75 ms 23636 KB Output is correct
40 Correct 96 ms 24340 KB Output is correct
41 Correct 92 ms 13772 KB Output is correct
42 Correct 63 ms 13260 KB Output is correct
43 Correct 78 ms 13040 KB Output is correct
44 Correct 50 ms 12844 KB Output is correct
45 Correct 74 ms 13360 KB Output is correct
46 Correct 53 ms 12708 KB Output is correct
47 Correct 77 ms 13348 KB Output is correct
48 Correct 54 ms 12628 KB Output is correct
49 Correct 61 ms 13212 KB Output is correct
50 Correct 44 ms 12344 KB Output is correct
51 Correct 46 ms 12924 KB Output is correct
52 Correct 43 ms 12560 KB Output is correct
53 Correct 47 ms 12352 KB Output is correct
54 Correct 44 ms 12928 KB Output is correct
55 Correct 44 ms 12656 KB Output is correct
56 Correct 17 ms 10580 KB Output is correct
57 Correct 43 ms 11340 KB Output is correct
58 Correct 39 ms 11748 KB Output is correct
59 Correct 0 ms 212 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 631 ms 61172 KB Output is correct
62 Correct 501 ms 59268 KB Output is correct
63 Correct 536 ms 57512 KB Output is correct
64 Correct 410 ms 57168 KB Output is correct
65 Correct 429 ms 59340 KB Output is correct
66 Correct 406 ms 56780 KB Output is correct
67 Correct 356 ms 57036 KB Output is correct
68 Correct 380 ms 54596 KB Output is correct
69 Correct 409 ms 57764 KB Output is correct
70 Correct 362 ms 53072 KB Output is correct
71 Correct 309 ms 55500 KB Output is correct
72 Correct 342 ms 53568 KB Output is correct
73 Correct 338 ms 53948 KB Output is correct
74 Correct 352 ms 56524 KB Output is correct
75 Correct 345 ms 55064 KB Output is correct
76 Correct 37 ms 22976 KB Output is correct
77 Correct 252 ms 40564 KB Output is correct
78 Correct 246 ms 44232 KB Output is correct
79 Correct 0 ms 212 KB Output is correct
80 Correct 1 ms 212 KB Output is correct