oj.uz

답안 #739728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739728 2023-05-11T07:07:34 Z danikoynov Abracadabra (CEOI22_abracadabra) C++14
40 / 100
 661 ms 109948 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 < tp; 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;
      |                                             ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 236 ms 41652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 661 ms 109948 KB Output is correct
2 Correct 634 ms 100608 KB Output is correct
3 Correct 574 ms 94248 KB Output is correct
4 Correct 375 ms 61560 KB Output is correct
5 Correct 429 ms 65212 KB Output is correct
6 Correct 349 ms 59596 KB Output is correct
7 Correct 368 ms 56640 KB Output is correct
8 Correct 365 ms 58268 KB Output is correct
9 Correct 384 ms 58544 KB Output is correct
10 Correct 300 ms 49180 KB Output is correct
11 Correct 230 ms 44964 KB Output is correct
12 Correct 246 ms 46380 KB Output is correct
13 Correct 285 ms 48240 KB Output is correct
14 Correct 258 ms 46408 KB Output is correct
15 Correct 285 ms 48812 KB Output is correct
16 Correct 35 ms 25164 KB Output is correct
17 Correct 498 ms 92144 KB Output is correct
18 Correct 187 ms 43852 KB Output is correct
19 Correct 72 ms 28744 KB Output is correct
20 Correct 99 ms 32980 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 206 ms 56224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 236 ms 41652 KB Output isn't correct
2 Halted 0 ms 0 KB -