oj.uz

Submission #698455

# Submission time Handle Problem Language Result Execution time Memory
698455 2023-02-13T14:04:26 Z Cyanmond Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 61288 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int B = 100;

struct SuperArray {
    std::vector<std::vector<int>> data;
    std::vector<int> maxVal;
    int blocks, countOp;
    
    SuperArray(std::vector<int> A) {
        data.push_back(A);
        rebuild();        
    }

    void rebuild() {
        std::vector<int> a;
        for (auto &vec : data) {
            std::copy(vec.begin(), vec.end(), std::back_inserter(a));
        }
        data.clear();
        const int n = (int)a.size();
        blocks = (n + B - 1) / B;
        data.resize(blocks);
        maxVal.assign(blocks, -1);
        for (int x = 0; x < blocks; ++x) {
            for (int i = x * B; i < std::min((x + 1) * B, n); ++i) {
                data[x].push_back(a[i]);
                maxVal[x] = std::max(maxVal[x], a[i]);
            }
        }
        countOp = 0;
    }

    void incOp() {
        ++countOp;
        if (countOp >= B) {
            rebuild();
        }
    }

    int get(int i) {
        int sum = 0;
        int ret = -1;
        for (const auto &vec : data) {
            if (sum + (int)vec.size() <= i) {
                sum += (int)vec.size();
            } else {
                ret = vec[i - sum];
                break;
            }
        }
        return ret;
    }

    void recalc(int x) {
        maxVal[x] = -1;
        for (const auto e : data[x]) {
            maxVal[x] = std::max(maxVal[x], e);
        }
    }

    void erase(int i) {
        incOp();
        int sum = 0;
        for (int x = 0; x < blocks; ++x) {
            auto &vec = data[x];
            if (sum + (int)vec.size() <= i) {
                sum += (int)vec.size();
            } else {
                vec.erase(vec.begin() + (i - sum));
                recalc(x);
                break;
            }
        }
    }

    int find(int l, int v) {
        int sum = 0;
        for (int x = 0; x < blocks; ++x) {
            if (sum + (int)data[x].size() <= l or maxVal[x] < v) {
                sum += (int)data[x].size();
            } else {
                for (int i = std::max(0, l - sum); i < (int)data[x].size(); ++i) {
                    if (data[x][i] >= v) {
                        return sum + i;
                    }
                }
            }
        }
        return sum;
    }

    void insert(int i, int v) {
        incOp();
        int sum = 0;
        for (int x = 0; x < blocks; ++x) {
            auto &vec = data[x];
            if (sum + (int)vec.size() <= i) {
                sum += (int)vec.size();
            } else {
                vec.insert(vec.begin() + (i - sum), v);
                recalc(x);
                break;
            }
        }
    }
};

struct Query {
    i64 t;
    int i;
    int queryId;
};

void solve(int N, int Q, std::vector<int> P, std::vector<std::pair<i64, int>> queries) {
    std::vector<Query> qs(Q);
    for (int i = 0; i < Q; ++i) {
        qs[i] = {queries[i].first, queries[i].second, i};
    }
    std::sort(qs.begin(), qs.end(), [](auto a, auto b) {
        return a.t < b.t;
    });
    SuperArray ar(P);
    std::vector<int> answer(Q);
    auto answerQuery = [&](const int t) {
        static int i = 0;
        if (t == -1) {
            while (i != Q) {
                answer[qs[i].queryId] = ar.get(qs[i].i);
                ++i;
            }
        } else {
            while (i != Q and qs[i].t == t) {
                answer[qs[i].queryId] = ar.get(qs[i].i);
                ++i;
            }
        }
    };
    answerQuery(0);

    int countShuffle = 0, minPos = N;
    for (int v = N; v >= 1; --v) {
        if (minPos == N / 2) {
            break;
        }
        const int pos = ar.find(0, v);
        if (pos >= N / 2) {
            minPos = std::min(minPos, pos);
            continue;
        }
        const int w = minPos - N / 2;
        const int dist = N / 2 - pos;
        const int c = (dist + w - 1) / w;
        for (int gomi = 0; gomi < c; ++gomi) {
            int l = 0;
            for (int i = N / 2; i < minPos; ++i) {
                const int val = ar.get(i);
                int p = ar.find(l, val);
                if (p >= i) {
                    p = i;
                }
                ar.erase(i);
                ar.insert(p, val);
                l = p + 1;
            }
            answerQuery(++countShuffle);
        }
        minPos = std::min(minPos, ar.find(0, v));
    }
    answerQuery(-1);

    for (const auto e : answer) {
        std::cout << e << std::endl;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // O(N^2)
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> P(N);
    for (auto &e : P) {
        std::cin >> e;
    }
    std::vector<std::pair<i64, int>> queries(Q);
    for (auto &[t, i] : queries) {
        std::cin >> t >> i;
        --i;
    }
    solve(N, Q, P, queries);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1409 ms 61288 KB Output is correct
2 Correct 1333 ms 61252 KB Output is correct
3 Correct 1335 ms 58988 KB Output is correct
4 Correct 1255 ms 58760 KB Output is correct
5 Correct 1361 ms 61036 KB Output is correct
6 Correct 1227 ms 58620 KB Output is correct
7 Correct 1314 ms 61124 KB Output is correct
8 Correct 1346 ms 59120 KB Output is correct
9 Correct 1265 ms 58544 KB Output is correct
10 Correct 1304 ms 59440 KB Output is correct
11 Correct 1283 ms 59312 KB Output is correct
12 Correct 1245 ms 58164 KB Output is correct
13 Correct 1263 ms 59696 KB Output is correct
14 Correct 1311 ms 60264 KB Output is correct
15 Correct 1324 ms 60852 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1262 ms 58608 KB Output is correct
18 Correct 1233 ms 57760 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3013 ms 59664 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 3055 ms 9872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1409 ms 61288 KB Output is correct
2 Correct 1333 ms 61252 KB Output is correct
3 Correct 1335 ms 58988 KB Output is correct
4 Correct 1255 ms 58760 KB Output is correct
5 Correct 1361 ms 61036 KB Output is correct
6 Correct 1227 ms 58620 KB Output is correct
7 Correct 1314 ms 61124 KB Output is correct
8 Correct 1346 ms 59120 KB Output is correct
9 Correct 1265 ms 58544 KB Output is correct
10 Correct 1304 ms 59440 KB Output is correct
11 Correct 1283 ms 59312 KB Output is correct
12 Correct 1245 ms 58164 KB Output is correct
13 Correct 1263 ms 59696 KB Output is correct
14 Correct 1311 ms 60264 KB Output is correct
15 Correct 1324 ms 60852 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1262 ms 58608 KB Output is correct
18 Correct 1233 ms 57760 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Execution timed out 3013 ms 59664 KB Time limit exceeded
22 Halted 0 ms 0 KB -