oj.uz

Submission #1030020

# Submission time Handle Problem Language Result Execution time Memory
1030020 2024-07-21T16:16:19 Z mispertion Abracadabra (CEOI22_abracadabra) C++17
25 / 100
 327 ms 82108 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 2e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;
 
int mult(int a, int b) {
    return a * 1LL * b % mod;
}
 
int sum(int a, int b) {
    a %= mod;
    b %= mod; 
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}
 
int binpow(int a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return mult(binpow(a, n - 1), a);
    } else {
        int b = binpow(a, n / 2);
        return mult(b, b);
    }
}

struct fenwick{
    int bt[N];
    
    void add(int i, int x){
        for(; i < N; i = (i | (i + 1)))
            bt[i] += x;
    }

    int get(int r){
        int ret = 0;
        for(; r >= 0; r = (r & (r + 1)) - 1)
            ret += bt[r];
        return ret;
    }

    int get(int l, int r){
        return get(r) - get(l - 1);
    }
} f;

int n, q, a[N], nxt[N], csz, ans[N];
set<pair<int, pii>> st;
pii otr[N];
vector<pii> que[N];

void shuffle(){
    while(csz - (st.rbegin()->S.S - st.rbegin()->S.F + 1) >= n / 2){
        csz -= (st.rbegin()->S.S - st.rbegin()->S.F + 1);
        st.erase(*st.rbegin());
    }
    if(csz == n / 2)
        return;
    pair<int, pii> pr = *st.rbegin();
    f.add(pr.F, -(pr.S.S - pr.S.F + 1));
    st.erase(pr);
    int nd = n / 2 - (csz - (pr.S.S - pr.S.F + 1));
    f.add(pr.F, nd);
    otr[pr.F] = {pr.S.F, pr.S.F + nd - 1};
    st.insert({pr.F, {pr.S.F, pr.S.F + nd - 1}});
    int nl = pr.S.F + nd, nr = pr.S.S;
    while(nl <= nr){
        int r = nxt[nl];
        f.add(a[nl], min(r - 1, nr) - nl + 1);
        otr[a[nl]] = {nl, min(r - 1, nr)};
        st.insert({a[nl], {nl, min(r - 1, nr)}});
        nl = r;
    }
}

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= q; i++){
        int t, ps;
        cin >> t >> ps;
        t = min(t, n);
        que[t].pb({ps, i});
    }
    a[n + 1] = n + 1;
    for(int i = n; i >= 1; i--){
        nxt[i] = i + 1;
        while(a[i] > a[nxt[i]]){
            nxt[i] = nxt[nxt[i]];
        }
    }
    csz = n;
    int i = 1;
    while(i <= n){
        st.insert({a[i], {i, nxt[i] - 1}});
        f.add(a[i], nxt[i] - i);
        otr[a[i]] = {i, nxt[i] - 1};
        i = nxt[i];
    }
    for(int i = 0; i <= n; i++){
        for(auto qu : que[i]){
            int ps = qu.F;
            int lo = 0, hi = n + 1;
            while(lo + 1 < hi){
                int m = (lo + hi) / 2;
                if(f.get(m) < ps)
                    lo = m;
                else
                    hi = m;
            }
            int ha = ps - f.get(hi - 1);
            ans[qu.S] = a[otr[hi].F + ha - 1];
        }
        shuffle();
    }
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

// coded by mispertion :)

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 74972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 82108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 21980 KB Output is correct
2 Correct 88 ms 23148 KB Output is correct
3 Correct 91 ms 21344 KB Output is correct
4 Correct 56 ms 18688 KB Output is correct
5 Correct 74 ms 21340 KB Output is correct
6 Correct 50 ms 18948 KB Output is correct
7 Correct 75 ms 20324 KB Output is correct
8 Correct 56 ms 19696 KB Output is correct
9 Correct 75 ms 20304 KB Output is correct
10 Correct 47 ms 18000 KB Output is correct
11 Correct 46 ms 18532 KB Output is correct
12 Correct 37 ms 18256 KB Output is correct
13 Correct 58 ms 18004 KB Output is correct
14 Correct 52 ms 18252 KB Output is correct
15 Correct 43 ms 17816 KB Output is correct
16 Correct 12 ms 14424 KB Output is correct
17 Correct 70 ms 23060 KB Output is correct
18 Correct 48 ms 16324 KB Output is correct
19 Correct 2 ms 12888 KB Output is correct
20 Correct 2 ms 13148 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 74972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -