Submission #709076

#	Time	Username	Problem	Language	Result	Execution time	Memory
709076		vjudge1	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	3077 ms	48256 KiB

Main

//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")*/

#define Respa return
#define gold 0

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 3e5 + 7;
const int K = 5e2 + 7;
const int MAXA = 5e4 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const ll MOD = (1ll << 30);

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

#define int long long

int n, q, a[N], b[N], ans[N];
void f() {
    vector <int> av, bv;
    for (int i = 1;i <= n / 2;i++)av.pb(a[i]);
    for (int i = n / 2 + 1;i <= n;i++)bv.pb(a[i]);
    av.pb(INF), bv.pb(INF);
    int l = 0, r = 0, pos = 0;
    while (l < n / 2 || r < n / 2) {
        if (av[l] <= bv[r])b[++pos] = av[l++];
        else b[++pos] = bv[r++];
    }
    for (int i = 1;i <= n;i++)a[i] = b[i];// cout << b[i] << ' ';
    //cout << '\n';
}
void solve() {
    cin >> n >> q;
    vector <pair <pii, int>> qs;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= q;i++) {
        int t, p;
        cin >> t >> p;
        qs.pb({{t, p}, i});
    }
    sort(all(qs));
    int last = 0;
    for (int i = 0;i < q;i++) {
        int t = qs[i].x.x, pos = qs[i].x.y, id = qs[i].y;
        if (t - last == 0)ans[id] = a[pos];
        else {
            if (t > n)ans[id] = a[pos];
            else {
                int x = t - last;
                while (x--)f();
                ans[id] = a[pos];
            }
        }
        last = t;
    }
    for (int i = 1;i <= q;i++)cout << ans[i] << '\n';
}
signed main() {
    //srand(time(NULL));
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("G.in", "r", stdin);
    //freopen("G.out", "w", stdout);
    int test = 1;
    //cin >> test;
    for (int i = 1;i <= test;i++) {
        //cout << "Case " << i << ": ";
        solve();
    }
    Respa gold;//2022-2023 InshAllah
}

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