oj.uz

Submission #1014464

# Submission time Handle Problem Language Result Execution time Memory
1014464 2024-07-05T00:59:39 Z shiomusubi496 Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1610 ms 52712 KB 
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(v) begin(v), end(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

class BinaryIndexedTree {
    int n;
    vector<int> dat;

public:
    BinaryIndexedTree(int n_) : n(n_), dat(n_ + 1, 0) {}
    void add(int k, ll x) {
        ++k;
        while (k <= n) {
            dat[k] += x;
            k += k & -k;
        }
    }
    ll sum(int k) const {
        ll res = 0;
        while (k > 0) {
            res += dat[k];
            k -= k & -k;
        }
        return res;
    }
    ll sum(int l, int r) const { return sum(r) - sum(l); }

    ll get(int k) const { return sum(k, k + 1); }

    template<class F> int max_right(F&& f) const {
        int x = 0;
        ll w = 0;
        for (int k = 1 << 20; k > 0; k >>= 1) {
            if (x + k <= n && f(w + dat[x + k])) {
                w += dat[x + k];
                x += k;
            }
        }
        return x;
    }
};

int main() {
    int N, Q; cin >> N >> Q;
    vector<int> A(N);
    rep (i, N) cin >> A[i];
    rep (i, N) --A[i];
    int M = 2 * N;
    vector<vector<pair<int, int>>> query(M);
    vector<int> ans(Q, -1);
    rep (i, Q) {
        int t, k; cin >> t >> k;
        chmin(t, M);
        --k;
        if (t == 0) ans[i] = A[k];
        else query[t - 1].emplace_back(k, i);
    }

    vector<int> nxt(N, N); // 自分より大きい最初の要素
    vector<int> len(N); // prefix で最大値を取るものについて、それが支配する区間の長さ
    {
        stack<int> st{{N}};
        rrep (i, N) {
            while (st.top() != N && A[st.top()] < A[i]) st.pop();
            nxt[i] = st.top();
            st.push(i);
        }
        while (st.top() != N) {
            len[st.top()] = nxt[st.top()] - st.top();
            st.pop();
        }
    }

    vector<int> Arev(N);
    rep (i, N) Arev[A[i]] = i;

    BinaryIndexedTree bit(N);
    rep (i, N) bit.add(A[i], len[i]);

    for (auto qs : query) {
        int a = bit.max_right([&](int w) { return w <= N / 2; });
        int t = N / 2 - bit.sum(a);
        a = Arev[a];
        if (t) {
            // A[a] が支配する区間が分割される
            int l = a + len[a];
            bit.add(A[a], t - len[a]);
            len[a] = t;
            a += t;
            while (a < l) {
                int na = min(nxt[a], l);
                bit.add(A[a], na - a);
                len[a] = na - a;
                a = na;
            }
        }
        for (auto [k, i] : qs) {
            int a = bit.max_right([&](int w) { return w <= k; });
            int t = k - bit.sum(a);
            a = Arev[a];
            ans[i] = A[a + t];
        }
    }
    for (auto i : ans) cout << i + 1 << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1184 ms 26304 KB Output is correct
2 Correct 1165 ms 24636 KB Output is correct
3 Correct 1172 ms 24092 KB Output is correct
4 Correct 1191 ms 22352 KB Output is correct
5 Correct 1135 ms 25940 KB Output is correct
6 Correct 1049 ms 25948 KB Output is correct
7 Correct 1143 ms 27136 KB Output is correct
8 Correct 1114 ms 24148 KB Output is correct
9 Correct 1120 ms 23376 KB Output is correct
10 Correct 1122 ms 22864 KB Output is correct
11 Correct 1068 ms 23136 KB Output is correct
12 Correct 1032 ms 21100 KB Output is correct
13 Correct 1053 ms 21796 KB Output is correct
14 Correct 1097 ms 25144 KB Output is correct
15 Correct 1140 ms 22376 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1137 ms 13640 KB Output is correct
18 Correct 1117 ms 17336 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1415 ms 47536 KB Output is correct
2 Correct 1415 ms 47276 KB Output is correct
3 Correct 1082 ms 39596 KB Output is correct
4 Correct 1030 ms 39340 KB Output is correct
5 Correct 1083 ms 40108 KB Output is correct
6 Correct 1047 ms 38572 KB Output is correct
7 Correct 1358 ms 46224 KB Output is correct
8 Correct 1229 ms 44464 KB Output is correct
9 Correct 1008 ms 39928 KB Output is correct
10 Correct 1278 ms 43372 KB Output is correct
11 Correct 1068 ms 38364 KB Output is correct
12 Correct 1046 ms 37744 KB Output is correct
13 Correct 1310 ms 42664 KB Output is correct
14 Correct 1047 ms 39084 KB Output is correct
15 Correct 1371 ms 44544 KB Output is correct
16 Correct 56 ms 14932 KB Output is correct
17 Correct 1123 ms 32328 KB Output is correct
18 Correct 952 ms 35832 KB Output is correct
19 Correct 267 ms 18256 KB Output is correct
20 Correct 314 ms 21232 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 11860 KB Output is correct
2 Correct 172 ms 11600 KB Output is correct
3 Correct 165 ms 11348 KB Output is correct
4 Correct 158 ms 10660 KB Output is correct
5 Correct 180 ms 11348 KB Output is correct
6 Correct 152 ms 10580 KB Output is correct
7 Correct 147 ms 11344 KB Output is correct
8 Correct 138 ms 10584 KB Output is correct
9 Correct 157 ms 11088 KB Output is correct
10 Correct 146 ms 10244 KB Output is correct
11 Correct 170 ms 10836 KB Output is correct
12 Correct 152 ms 10324 KB Output is correct
13 Correct 174 ms 10336 KB Output is correct
14 Correct 149 ms 10576 KB Output is correct
15 Correct 154 ms 10324 KB Output is correct
16 Correct 25 ms 7516 KB Output is correct
17 Correct 138 ms 8992 KB Output is correct
18 Correct 138 ms 9556 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1184 ms 26304 KB Output is correct
2 Correct 1165 ms 24636 KB Output is correct
3 Correct 1172 ms 24092 KB Output is correct
4 Correct 1191 ms 22352 KB Output is correct
5 Correct 1135 ms 25940 KB Output is correct
6 Correct 1049 ms 25948 KB Output is correct
7 Correct 1143 ms 27136 KB Output is correct
8 Correct 1114 ms 24148 KB Output is correct
9 Correct 1120 ms 23376 KB Output is correct
10 Correct 1122 ms 22864 KB Output is correct
11 Correct 1068 ms 23136 KB Output is correct
12 Correct 1032 ms 21100 KB Output is correct
13 Correct 1053 ms 21796 KB Output is correct
14 Correct 1097 ms 25144 KB Output is correct
15 Correct 1140 ms 22376 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1137 ms 13640 KB Output is correct
18 Correct 1117 ms 17336 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1415 ms 47536 KB Output is correct
22 Correct 1415 ms 47276 KB Output is correct
23 Correct 1082 ms 39596 KB Output is correct
24 Correct 1030 ms 39340 KB Output is correct
25 Correct 1083 ms 40108 KB Output is correct
26 Correct 1047 ms 38572 KB Output is correct
27 Correct 1358 ms 46224 KB Output is correct
28 Correct 1229 ms 44464 KB Output is correct
29 Correct 1008 ms 39928 KB Output is correct
30 Correct 1278 ms 43372 KB Output is correct
31 Correct 1068 ms 38364 KB Output is correct
32 Correct 1046 ms 37744 KB Output is correct
33 Correct 1310 ms 42664 KB Output is correct
34 Correct 1047 ms 39084 KB Output is correct
35 Correct 1371 ms 44544 KB Output is correct
36 Correct 56 ms 14932 KB Output is correct
37 Correct 1123 ms 32328 KB Output is correct
38 Correct 952 ms 35832 KB Output is correct
39 Correct 267 ms 18256 KB Output is correct
40 Correct 314 ms 21232 KB Output is correct
41 Correct 169 ms 11860 KB Output is correct
42 Correct 172 ms 11600 KB Output is correct
43 Correct 165 ms 11348 KB Output is correct
44 Correct 158 ms 10660 KB Output is correct
45 Correct 180 ms 11348 KB Output is correct
46 Correct 152 ms 10580 KB Output is correct
47 Correct 147 ms 11344 KB Output is correct
48 Correct 138 ms 10584 KB Output is correct
49 Correct 157 ms 11088 KB Output is correct
50 Correct 146 ms 10244 KB Output is correct
51 Correct 170 ms 10836 KB Output is correct
52 Correct 152 ms 10324 KB Output is correct
53 Correct 174 ms 10336 KB Output is correct
54 Correct 149 ms 10576 KB Output is correct
55 Correct 154 ms 10324 KB Output is correct
56 Correct 25 ms 7516 KB Output is correct
57 Correct 138 ms 8992 KB Output is correct
58 Correct 138 ms 9556 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1610 ms 52712 KB Output is correct
62 Correct 1460 ms 51380 KB Output is correct
63 Correct 1493 ms 49840 KB Output is correct
64 Correct 1358 ms 49052 KB Output is correct
65 Correct 1451 ms 50988 KB Output is correct
66 Correct 1494 ms 48980 KB Output is correct
67 Correct 1253 ms 48716 KB Output is correct
68 Correct 1250 ms 46664 KB Output is correct
69 Correct 1284 ms 49324 KB Output is correct
70 Correct 1255 ms 45240 KB Output is correct
71 Correct 1277 ms 46932 KB Output is correct
72 Correct 1321 ms 45732 KB Output is correct
73 Correct 1357 ms 46096 KB Output is correct
74 Correct 1262 ms 48464 KB Output is correct
75 Correct 1358 ms 46752 KB Output is correct
76 Correct 68 ms 14676 KB Output is correct
77 Correct 1208 ms 32512 KB Output is correct
78 Correct 1176 ms 36260 KB Output is correct
79 Correct 0 ms 344 KB Output is correct
80 Correct 0 ms 348 KB Output is correct