oj.uz

Submission #668970

# Submission time Handle Problem Language Result Execution time Memory
668970 2022-12-05T09:58:02 Z boris_mihov Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 19788 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>

typedef long long llong;
const int MAXQ = 1000000 + 10;
const int MAXN = 200000 + 10;
const int INF = 1e9 + 1;

struct Query
{
    int idx;
    int pos;
    int time;

    inline friend bool operator < (const Query &a, const Query &b)
    {
        return a.time < b.time || (a.time == b.time && a.idx < b.idx);
    }
};

int n, q;
int a[MAXN];
int b[MAXN];
Query queries[MAXQ];
int ans[MAXQ];

void solve()
{
    int qPtr = 1;
    bool areEqual = false;
    std::sort(queries + 1, queries + 1 + q);
    for (int shuffle = 0; shuffle <= n ; ++shuffle)
    {
        while (qPtr <= q && queries[qPtr].time == shuffle)
        {
            ans[queries[qPtr].idx] = a[queries[qPtr].pos];
            qPtr++;
        } 
        int lPtr = 1, rPtr = n/2 + 1, ptr = 1;
        while (lPtr <= n/2 || rPtr <= n)
        {
            if (lPtr == n/2 + 1)
            {
                b[ptr++] = a[rPtr++];
                continue;
            }

            if (rPtr == n + 1)
            {
                b[ptr++] = a[lPtr++];
                continue;
            }

            if (a[lPtr] < a[rPtr])
            {
                b[ptr++] = a[lPtr++];
                continue;
            } else
            {
                b[ptr++] = a[rPtr++];
                continue;
            }
        }

        areEqual = true;
        for (int i = 1 ; i <= n ; ++i)
        {
            areEqual &= (a[i] == b[i]);
            a[i] = b[i];
        }
    }

    while (qPtr <= q) 
    {
        ans[queries[qPtr].idx] = a[queries[qPtr].pos];
        qPtr++;
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << ans[i] << '\n';
    }
}

void read()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> queries[i].time >> queries[i].pos;
        queries[i].idx = i;
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 19768 KB Output is correct
2 Correct 282 ms 19788 KB Output is correct
3 Correct 279 ms 19032 KB Output is correct
4 Correct 271 ms 18944 KB Output is correct
5 Correct 289 ms 19700 KB Output is correct
6 Correct 268 ms 18944 KB Output is correct
7 Correct 298 ms 19776 KB Output is correct
8 Correct 276 ms 19020 KB Output is correct
9 Correct 268 ms 18872 KB Output is correct
10 Correct 285 ms 19184 KB Output is correct
11 Correct 273 ms 19164 KB Output is correct
12 Correct 265 ms 18956 KB Output is correct
13 Correct 270 ms 19356 KB Output is correct
14 Correct 300 ms 19580 KB Output is correct
15 Correct 285 ms 19788 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 258 ms 19224 KB Output is correct
18 Correct 247 ms 19016 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 13504 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 3078 ms 2636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 19768 KB Output is correct
2 Correct 282 ms 19788 KB Output is correct
3 Correct 279 ms 19032 KB Output is correct
4 Correct 271 ms 18944 KB Output is correct
5 Correct 289 ms 19700 KB Output is correct
6 Correct 268 ms 18944 KB Output is correct
7 Correct 298 ms 19776 KB Output is correct
8 Correct 276 ms 19020 KB Output is correct
9 Correct 268 ms 18872 KB Output is correct
10 Correct 285 ms 19184 KB Output is correct
11 Correct 273 ms 19164 KB Output is correct
12 Correct 265 ms 18956 KB Output is correct
13 Correct 270 ms 19356 KB Output is correct
14 Correct 300 ms 19580 KB Output is correct
15 Correct 285 ms 19788 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 258 ms 19224 KB Output is correct
18 Correct 247 ms 19016 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Execution timed out 3049 ms 13504 KB Time limit exceeded
22 Halted 0 ms 0 KB -