oj.uz

Submission #739729

# Submission time Handle Problem Language Result Execution time Memory
739729 2023-05-11T07:08:29 Z danikoynov Abracadabra (CEOI22_abracadabra) C++14
100 / 100
 1119 ms 132232 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10, maxq = 1e6 + 10;

int n, q, a[maxn], b[maxn], ans[maxq], nxt_pos[maxn], nxt_val[maxn];
vector < pair < int, int > > ask[maxn];

void shuffle_array()
{
    deque < int > d1, d2;
    for (int i = 1; i <= n / 2; i ++)
        d1.push_back(a[i]);
    for (int i = n / 2 + 1; i <= n; i ++)
        d2.push_back(a[i]);

    deque < int > res;
    while(!d1.empty() && !d2.empty())
    {
        if (d1.front() < d2.front())
        {
            res.push_back(d1.front());
            d1.pop_front();
        }
        else
        {
            res.push_back(d2.front());
            d2.pop_front();
        }
    }

    while(!d1.empty())
    {
        res.push_back(d1.front());
        d1.pop_front();
    }

    while(!d2.empty())
    {
        res.push_back(d2.front());
        d2.pop_front();
    }

    for (int i = 1; i <= n; i ++)
        a[i] = res[i - 1];
}

struct block
{
    int val, left, right;

    block(int _val = 0, int _left = 0, int _right = 0)
    {
        val = _val;
        left = _left;
        right = _right;
    }
    bool operator < (const block &bk) const
    {
        if (val == bk.val)
            return right < bk.right;

        return val < bk.val;
    }
};
set < block > act, blocks;
int fin[maxn], to, sz;

void shuffle_smart_init()
{

    while(true)
    {
        block cur = *act.rbegin();
        if (sz - (cur.right - cur.left + 1) + 1 > n / 2)
        {
            ///cout << "remove " << sz << " " << cur.left << " " << cur.right << endl;
            act.erase(cur);
            sz -= (cur.right - cur.left + 1);
        }
        else
        {
            break;
        }
    }

    if (sz == n / 2)
        return;
    /** for (block cur : act)
    {
     cout << "here " << cur.val << " " << cur.left << " " << cur.right << endl;
    }*/
    block cur = *act.rbegin();
    act.erase(cur);
    block fr = cur;
    fr.right = cur.right - (sz - n / 2);
    act.insert(fr);
    blocks.insert(fr);
    int idx = cur.right - (sz - n / 2) + 1, svd = idx;
    int sum_size = 0;
    //cout << idx << " : " << cur.right << endl;
    while(idx <= cur.right)
    {
        int gt = nxt_pos[idx];
        gt = min(gt, cur.right + 1);
        sum_size += (gt - idx);
        act.insert(block(a[idx], idx, gt - 1));
        blocks.insert(block(a[idx], idx, gt - 1));
        idx = gt;
    }
}

unordered_map < int, int > rev[maxn];
block bl[maxn * 2];
int tree[8 * maxn];
int bl_cnt;

void update(int root, int left, int right, int idx)
{
    if (left == right)
    {
        if (tree[root] == 0)
            tree[root] = bl[left].right - bl[left].left + 1;
        else
            tree[root] = 0;
        return;
    }

    int mid = (left + right) / 2;
    if (idx <= mid)
        update(root * 2, left, mid, idx);
    else
        update(root * 2 + 1, mid + 1, right, idx);

    tree[root] = tree[root * 2] + tree[root * 2 + 1];
}

int walk(int root, int left, int right, int k)
{
    if (left == right)
    {
        return a[bl[left].left + k - 1];
    }

    int mid = (left + right) / 2;
    if (tree[root * 2] >= k)
        return   walk(root * 2, left, mid, k);
    else
        return walk(root * 2 + 1, mid + 1, right, k - tree[root * 2]);
}


void shuffle_smart()
{

    while(true)
    {
        block cur = *act.rbegin();
        if (sz - (cur.right - cur.left + 1) + 1 > n / 2)
        {
            ///cout << "remove " << sz << " " << cur.left << " " << cur.right << endl;
            act.erase(cur);
            sz -= (cur.right - cur.left + 1);
        }
        else
        {
            break;
        }
    }

    if (sz == n / 2)
        return;
    /** for (block cur : act)
    {
     cout << "here " << cur.val << " " << cur.left << " " << cur.right << endl;
    }*/
    block cur = *act.rbegin();
    act.erase(cur);
    update(1, 1, bl_cnt, rev[cur.left][cur.right]);
    block fr = cur;
    fr.right = cur.right - (sz - n / 2);
    act.insert(fr);
    update(1, 1, bl_cnt, rev[fr.left][fr.right]);
    int idx = cur.right - (sz - n / 2) + 1, svd = idx;
    int sum_size = 0;
    //cout << idx << " : " << cur.right << endl;
    while(idx <= cur.right)
    {
        int gt = nxt_pos[idx];
        gt = min(gt, cur.right + 1);
        sum_size += (gt - idx);
        act.insert(block(a[idx], idx, gt - 1));
        update(1, 1, bl_cnt, rev[idx][gt - 1]);
        idx = gt;
    }
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        b[i] = a[i];
    }

    int tp = 0;
    for (int i = 1; i <= q; i ++)
    {
        int t, v;
        cin >> t >> v;
        t = min(t, n);
        tp = t;
        if (t == 0)
            ans[i] = a[v];
        else
            ask[t].push_back({v, i});
    }

    shuffle_array();
    /**for (int i = 1; i <= n; i ++)
        cout << a[i] << " ";
    cout << endl;*/
    stack < int > st;
    for (int i = 1; i <= n; i ++)
    {
        while(!st.empty() && a[st.top()] < a[i])
        {
            nxt_pos[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty())
    {
        nxt_pos[st.top()] = n + 1;
        st.pop();
    }

    int i = 1;
    while(i <= n)
    {
        act.insert(block(a[i], i, nxt_pos[i] - 1));
        blocks.insert(block(a[i], i, nxt_pos[i] - 1));
        i = nxt_pos[i];
    }


    to = n;
    sz = n;

    for (int f = 1; f <= n; f ++)
    {
        shuffle_smart_init();
    }

    while(!act.empty())
    {
        block cur = *act.rbegin();    ///cout << to << " " << sz << " " << (cur.right - cur.left + 1) << endl;

        act.erase(cur);
        sz -= (cur.right - cur.left + 1);
    }

    for (block cur : blocks)
    {
        rev[cur.left][cur.right] = ++ bl_cnt;
        bl[bl_cnt] = cur;
        ///cout << cur.val << " " << cur.left << " " << cur.right << endl;
    }

    for (int i = 1; i <= n; i ++)
        a[i] = b[i];
    shuffle_array();

    i = 1;
    while(i <= n)
    {
        act.insert(block(a[i], i, nxt_pos[i] - 1));
                update(1, 1, bl_cnt, rev[i][nxt_pos[i] - 1]);
        ///blocks.insert(block(a[i], i, nxt_pos[i] - 1));
        i = nxt_pos[i];
    }


    to = n;
    sz = n;

    for (int f = 1; f <= n; f ++)
    {
        for (pair < int, int > cur : ask[f])
        {
            ans[cur.second] = walk(1, 1, bl_cnt, cur.first);
        }
        shuffle_smart();
    }


    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
}
int main()
{
    speed();
    solve();
    return 0;
}
/**
10 0
3 8 2 4 9 5 10 1 6 7
*/

Compilation message

Main.cpp: In function 'void shuffle_smart_init()':
Main.cpp:117:45: warning: unused variable 'svd' [-Wunused-variable]
  117 |     int idx = cur.right - (sz - n / 2) + 1, svd = idx;
      |                                             ^~~
Main.cpp: In function 'void shuffle_smart()':
Main.cpp:202:45: warning: unused variable 'svd' [-Wunused-variable]
  202 |     int idx = cur.right - (sz - n / 2) + 1, svd = idx;
      |                                             ^~~
Main.cpp: In function 'void solve()':
Main.cpp:224:9: warning: variable 'tp' set but not used [-Wunused-but-set-variable]
  224 |     int tp = 0;
      |         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 38992 KB Output is correct
2 Correct 273 ms 40960 KB Output is correct
3 Correct 260 ms 40516 KB Output is correct
4 Correct 208 ms 39092 KB Output is correct
5 Correct 227 ms 42360 KB Output is correct
6 Correct 212 ms 42892 KB Output is correct
7 Correct 234 ms 43580 KB Output is correct
8 Correct 230 ms 41624 KB Output is correct
9 Correct 211 ms 40280 KB Output is correct
10 Correct 232 ms 40268 KB Output is correct
11 Correct 215 ms 40604 KB Output is correct
12 Correct 207 ms 37768 KB Output is correct
13 Correct 223 ms 39364 KB Output is correct
14 Correct 250 ms 42200 KB Output is correct
15 Correct 231 ms 39388 KB Output is correct
16 Correct 13 ms 20752 KB Output is correct
17 Correct 171 ms 31828 KB Output is correct
18 Correct 196 ms 35444 KB Output is correct
19 Correct 13 ms 20692 KB Output is correct
20 Correct 12 ms 20700 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 112628 KB Output is correct
2 Correct 668 ms 99188 KB Output is correct
3 Correct 713 ms 96264 KB Output is correct
4 Correct 406 ms 57240 KB Output is correct
5 Correct 441 ms 59408 KB Output is correct
6 Correct 417 ms 57384 KB Output is correct
7 Correct 395 ms 50840 KB Output is correct
8 Correct 449 ms 53144 KB Output is correct
9 Correct 381 ms 53292 KB Output is correct
10 Correct 306 ms 43836 KB Output is correct
11 Correct 250 ms 39088 KB Output is correct
12 Correct 266 ms 41164 KB Output is correct
13 Correct 302 ms 42680 KB Output is correct
14 Correct 304 ms 40548 KB Output is correct
15 Correct 288 ms 43304 KB Output is correct
16 Correct 40 ms 24276 KB Output is correct
17 Correct 451 ms 86380 KB Output is correct
18 Correct 194 ms 38036 KB Output is correct
19 Correct 72 ms 26316 KB Output is correct
20 Correct 104 ms 28632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 60640 KB Output is correct
2 Correct 216 ms 54724 KB Output is correct
3 Correct 254 ms 55432 KB Output is correct
4 Correct 82 ms 29932 KB Output is correct
5 Correct 199 ms 44112 KB Output is correct
6 Correct 85 ms 31204 KB Output is correct
7 Correct 144 ms 38156 KB Output is correct
8 Correct 117 ms 34536 KB Output is correct
9 Correct 152 ms 39140 KB Output is correct
10 Correct 50 ms 26444 KB Output is correct
11 Correct 59 ms 27196 KB Output is correct
12 Correct 53 ms 26336 KB Output is correct
13 Correct 54 ms 26852 KB Output is correct
14 Correct 55 ms 26700 KB Output is correct
15 Correct 48 ms 25932 KB Output is correct
16 Correct 25 ms 23628 KB Output is correct
17 Correct 163 ms 50636 KB Output is correct
18 Correct 40 ms 24848 KB Output is correct
19 Correct 11 ms 20664 KB Output is correct
20 Correct 12 ms 20700 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 38992 KB Output is correct
2 Correct 273 ms 40960 KB Output is correct
3 Correct 260 ms 40516 KB Output is correct
4 Correct 208 ms 39092 KB Output is correct
5 Correct 227 ms 42360 KB Output is correct
6 Correct 212 ms 42892 KB Output is correct
7 Correct 234 ms 43580 KB Output is correct
8 Correct 230 ms 41624 KB Output is correct
9 Correct 211 ms 40280 KB Output is correct
10 Correct 232 ms 40268 KB Output is correct
11 Correct 215 ms 40604 KB Output is correct
12 Correct 207 ms 37768 KB Output is correct
13 Correct 223 ms 39364 KB Output is correct
14 Correct 250 ms 42200 KB Output is correct
15 Correct 231 ms 39388 KB Output is correct
16 Correct 13 ms 20752 KB Output is correct
17 Correct 171 ms 31828 KB Output is correct
18 Correct 196 ms 35444 KB Output is correct
19 Correct 13 ms 20692 KB Output is correct
20 Correct 12 ms 20700 KB Output is correct
21 Correct 742 ms 112628 KB Output is correct
22 Correct 668 ms 99188 KB Output is correct
23 Correct 713 ms 96264 KB Output is correct
24 Correct 406 ms 57240 KB Output is correct
25 Correct 441 ms 59408 KB Output is correct
26 Correct 417 ms 57384 KB Output is correct
27 Correct 395 ms 50840 KB Output is correct
28 Correct 449 ms 53144 KB Output is correct
29 Correct 381 ms 53292 KB Output is correct
30 Correct 306 ms 43836 KB Output is correct
31 Correct 250 ms 39088 KB Output is correct
32 Correct 266 ms 41164 KB Output is correct
33 Correct 302 ms 42680 KB Output is correct
34 Correct 304 ms 40548 KB Output is correct
35 Correct 288 ms 43304 KB Output is correct
36 Correct 40 ms 24276 KB Output is correct
37 Correct 451 ms 86380 KB Output is correct
38 Correct 194 ms 38036 KB Output is correct
39 Correct 72 ms 26316 KB Output is correct
40 Correct 104 ms 28632 KB Output is correct
41 Correct 265 ms 60640 KB Output is correct
42 Correct 216 ms 54724 KB Output is correct
43 Correct 254 ms 55432 KB Output is correct
44 Correct 82 ms 29932 KB Output is correct
45 Correct 199 ms 44112 KB Output is correct
46 Correct 85 ms 31204 KB Output is correct
47 Correct 144 ms 38156 KB Output is correct
48 Correct 117 ms 34536 KB Output is correct
49 Correct 152 ms 39140 KB Output is correct
50 Correct 50 ms 26444 KB Output is correct
51 Correct 59 ms 27196 KB Output is correct
52 Correct 53 ms 26336 KB Output is correct
53 Correct 54 ms 26852 KB Output is correct
54 Correct 55 ms 26700 KB Output is correct
55 Correct 48 ms 25932 KB Output is correct
56 Correct 25 ms 23628 KB Output is correct
57 Correct 163 ms 50636 KB Output is correct
58 Correct 40 ms 24848 KB Output is correct
59 Correct 11 ms 20664 KB Output is correct
60 Correct 12 ms 20700 KB Output is correct
61 Correct 1119 ms 132232 KB Output is correct
62 Correct 1002 ms 116324 KB Output is correct
63 Correct 948 ms 116936 KB Output is correct
64 Correct 613 ms 76992 KB Output is correct
65 Correct 662 ms 80572 KB Output is correct
66 Correct 620 ms 77336 KB Output is correct
67 Correct 502 ms 66044 KB Output is correct
68 Correct 492 ms 67812 KB Output is correct
69 Correct 561 ms 72904 KB Output is correct
70 Correct 363 ms 57420 KB Output is correct
71 Correct 323 ms 56720 KB Output is correct
72 Correct 360 ms 58060 KB Output is correct
73 Correct 325 ms 56776 KB Output is correct
74 Correct 355 ms 59608 KB Output is correct
75 Correct 331 ms 57424 KB Output is correct
76 Correct 36 ms 25428 KB Output is correct
77 Correct 485 ms 95436 KB Output is correct
78 Correct 250 ms 46744 KB Output is correct
79 Correct 12 ms 20692 KB Output is correct
80 Correct 11 ms 20692 KB Output is correct