Submission #866986

#	Time	Username	Problem	Language	Result	Execution time	Memory
866986		Lalic	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3012 ms	33456 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const ll inv2 = 500000004;

void solve(){
    int n, q; cin >> n >> q;

    vector<int> arr(n);
    int mx=0;
    for(int i=0;i<n;i++)
        cin >> arr[i], mx=max(mx, (i<n/2 ? arr[i] : -1));

    vector<pair<pii, int>> query(q);
    for(int i=0;i<q;i++)
        cin >> query[i].fi.fi >> query[i].fi.se, query[i].se=i;

    sort(all(query));

    vector<int> ans(q);
    int cnt=0;

    for(int i=0;i<q;i++){
        while(mx>arr[n/2] && cnt<query[i].fi.fi){
            cnt++;

            vector<int> att;
            mx=0;

            int ptr=n/2;
            for(int i=0;i<n/2;i++){
                while(ptr<n && arr[ptr]<arr[i]){
                    if((int)att.size()<n/2)
                        mx=max(mx, arr[ptr]);
                    att.pb(arr[ptr++]);
                }

                if((int)att.size()<n/2)
                    mx=max(mx, arr[i]);
                att.pb(arr[i]);
            }

            arr=att;
        }

        ans[query[i].se]=arr[query[i].fi.se-1];
    }

    for(int i=0;i<q;i++)
        cout << ans[i] << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    // freopen("fetiera.in", "r", stdin);

    int tt=1;
    // cin >> tt;
    while(tt--)
        solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25