oj.uz

답안 #739646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739646 2023-05-10T21:58:36 Z danikoynov Abracadabra (CEOI22_abracadabra) C++14
40 / 100
 710 ms 48368 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], 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, int _left, int _right)
    {
        val = _val;
        left = _left;
        right = _right;
    }
    bool operator < (const block &bk) const
    {
        return val < bk.val;
    }
};
set < block > act;
int fin[maxn], to, sz;
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;
            for (int i = cur.right; i >= cur.left; i --)
                fin[to --] = a[i];
            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);
    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));
        ///cout << idx << " -- " << gt << " " << sum_size << endl;
        idx = gt;
    }
    /**if (sum_size != (sz - n / 2))
    {
        cout << "wtf " << (sz - n / 2) <<  " "<< sum_size << endl;
         for (block cur : act)
    {
        cout << "here " << cur.val << " " << cur.left << " " << cur.right <<  " " << svd << endl;
    }
    }*/
   // cout << "------------" << endl;

}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> 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));
        i = nxt_pos[i];
    }


    to = n;
    sz = n;

    for (int f = 1; f < tp; f ++)
    {
        shuffle_smart();
    }
    while(!act.empty())
    {
        block cur = *act.rbegin();    ///cout << to << " " << sz << " " << (cur.right - cur.left + 1) << endl;
            for (int i = cur.right; i >= cur.left; i --)
                fin[to --] = a[i];

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

        for (pair < int, int > cur : ask[tp])
            ans[cur.second] = fin[cur.first];
    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
}
int main()
{
    ///speed();
    //freopen("test.txt", "r", stdin);
    ///freopen("output.txt", "w", stdout);
    solve();
    return 0;
}
/**
10 0
3 8 2 4 9 5 10 1 6 7
*/

Compilation message

Main.cpp: In function 'void shuffle_smart()':
Main.cpp:114:45: warning: unused variable 'svd' [-Wunused-variable]
  114 |     int idx = cur.right - (sz - n / 2) + 1, svd = idx;
      |                                             ^~~

Subtask #1
0 / 10.0

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

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 697 ms 29072 KB Output is correct
2 Correct 710 ms 48368 KB Output is correct
3 Correct 604 ms 38320 KB Output is correct
4 Correct 541 ms 34500 KB Output is correct
5 Correct 561 ms 36236 KB Output is correct
6 Correct 517 ms 33312 KB Output is correct
7 Correct 648 ms 40484 KB Output is correct
8 Correct 625 ms 39316 KB Output is correct
9 Correct 536 ms 35328 KB Output is correct
10 Correct 585 ms 37144 KB Output is correct
11 Correct 481 ms 31800 KB Output is correct
12 Correct 481 ms 31848 KB Output is correct
13 Correct 564 ms 36452 KB Output is correct
14 Correct 494 ms 32696 KB Output is correct
15 Correct 625 ms 38088 KB Output is correct
16 Correct 63 ms 9348 KB Output is correct
17 Correct 572 ms 38280 KB Output is correct
18 Correct 422 ms 29924 KB Output is correct
19 Correct 152 ms 12956 KB Output is correct
20 Correct 196 ms 16036 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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