Submission #698243

#	Time	Username	Problem	Language	Result	Execution time	Memory
698243		Kahou	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	583 ms	47276 KiB

Main

/* In the name of God, aka Allah */
// Believe me - Takeshi Abo
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50, M = 1e6 + 50, LG = 20;
int n, q, par[N], out[M];
vector<pii> vc[N];
int p[N], pp[N];
int fen[N];

void upd(int i, int x) {
        for (; i <= n; i += i&-i) fen[i] += x;
}
int get(int i) {
        int out = 0;
        for (; i > 0; i -= i&-i) out += fen[i];
        return out;
}
int getpos(int x) {
        int pos = 0;
        for (int k = LG-1; k >= 0; k--) {
                if (pos+(1<<k) <= n && fen[pos+(1<<k)] < x) {
                        pos ^= 1<<k;
                        x -= fen[pos];
                }
        }
        return pos+1;
}

void solve() {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
                cin >> p[i];
                pp[p[i]] = i;
        }
        for (int i = 1; i <= q; i++) {
                int t, k;
                cin >> t >> k;
                t = min(t, n);
                vc[t].push_back({k, i});
        }
        for (pii x:vc[0]) out[x.S] = p[x.F];
        for (int i = n; i >= 1; i--) {
                par[i] = i+1;
                while (par[i] <= n && p[i] > p[par[i]]) {
                        par[i] = par[par[i]];
                }
        }
        int pt = 1;
        while (pt <= n/2) {
                upd(p[pt], min(n/2+1, par[pt])-pt);
                pt = par[pt];
        }
        pt = n/2+1;
        while (pt <= n) {
                upd(p[pt], par[pt]-pt);
                pt = par[pt];
        }

        for (int tt = 1; tt <= n; tt++) {
                for (pii x:vc[tt]) {
                        int id = getpos(x.F);
                        out[x.S] = p[x.F-get(id-1)+pp[id]-1];
                }
                int id = getpos(n/2);
                if (get(id) <= n/2) continue;

                int pt = n/2-get(id-1)+pp[id];
                int ft = get(id)-get(id-1)+pp[id]-1;
                upd(id, n/2-get(id));
                while (pt <= ft) {
                        upd(p[pt], min(par[pt], ft+1)-pt);
                        pt = par[pt];
                }
        }

        for (int i = 1; i <= q; i++) {
                cout << out[i] << endl;
        }
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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