oj.uz

Submission #698235

# Submission time Handle Problem Language Result Execution time Memory
698235 2023-02-12T23:13:10 Z Kahou Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 303 ms 25396 KB 
/* 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];
bool mark[N];
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;
        mark[n+1] = 1;
        while (pt <= n/2 && !mark[pt]) {
                mark[pt] = 1;
                upd(p[pt], min(n/2+1, par[pt])-pt);
                pt = par[pt];
        }
        pt = n/2+1;
        while (!mark[pt]) {
                mark[pt] = 1;
                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];
                upd(id, n/2-get(id));
                while (!mark[pt]) {
                        mark[pt] = 1;
                        upd(p[pt], par[pt]-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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 251 ms 23024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 25396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 251 ms 23024 KB Output isn't correct
2 Halted 0 ms 0 KB -