제출 #1030024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030024		mispertion	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	787 ms	73348 KiB

Main

#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[1000005];
set<pair<int, pii>> st;
pii otr[N];
vector<pii> que[N];

void shuffle(){
    while(sz(st) > 0 && 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: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25