제출 #1235679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235679		jasonic	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	229 ms	47568 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

int sznost[200005]; 

struct ST{
    int l, r;
    ST *lt, *rt;
    int sz;

    void comb() {
        sz = lt->sz + rt->sz;
    }

    ST(int bl, int br) {
        l = bl, r = br;
        lt = rt = nullptr;
        sz = 0;
        if(l != r) {
            int m = (l+r)/2;
            lt = new ST(l, m);
            rt = new ST(m+1, r);
        }
    }

    int get(int i) {
        if(l == r) return sz;
        if(lt->r < i) return rt->get(i);
        else return lt->get(i);
    }

    void set(int i, int x) {
        if(l == r) {
            sznost[i] = x;
            sz = x;
        } else {
            if(i <= lt->r) lt->set(i, x);
            else rt->set(i, x);
            comb();
        }
    }

    // returns the leader (and the ) of the group that contains the value at the i-th index
    pair<int, int> find(int i) {
        if(l == r) return make_pair(l, i);
        if(lt->sz < i) return rt->find(i - (lt->sz));
        return lt->find(i);
    }
};

int main() {
    fastIO;
    
    int n, q; cin >> n >> q;
    vector<int> a(n); for(auto &i : a) cin >> i;
    
    struct Query{
        int t, i, qi, ans;
        Query(int a, int b, int c): t(a), i(b), qi(c), ans(-1) {};
        bool operator<(const Query &other) const {
            return t < other.t;
        }
    };
    vector<Query> qs;
    qs.reserve(q);

    for(int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        qs.push_back(Query(min(a, n+2), b, i));
    }
    sort(qs.begin(), qs.end());

    vector<int> rev(n);
    vector<int> nextpoint(n);
    vector<int> theoreticalSize(n);
    ST szs(0, n-1);

    for(int i = 0; i < n; i++) {
        a[i]--;
        rev[a[i]] = i;
    }

    stack<pair<int, int>> maxstack;
    maxstack.push({n+1, n});

    for(int i = n-1; i >= 0; i--) {
        while(a[i] > maxstack.top().first) {
            maxstack.pop();
        }
        theoreticalSize[i] = maxstack.top().second - i;
        nextpoint[i] = maxstack.top().second;

        maxstack.push({a[i], i});
    }

    bool fixed = false;

    auto reprocessrange = [&](int s, int t) {
        int x = s;
        while(x < t) {
            // printf("idx: %d\n", x);
            szs.set(a[x], theoreticalSize[x]);
            x = nextpoint[x];
        }
        // printf("udpate:\n");
        // for(int i = 0; i < n; i++) printf("%d %d\n", i, szs.get(i));
        // printf("\n");
    };

    int time = 0;

    auto update = [&](){
        pair<int, int> lead = szs.find(n/2 + 1);
        // printf("update! leader is %d, and the index is %d.\n", lead.first, lead.second);

        if(lead.second == 1) {
            fixed = true;
            return;
        }

        int sz = szs.get(lead.first);

        reprocessrange(rev[lead.first]+lead.second-1, rev[lead.first]+sz);
        szs.set(lead.first, lead.second-1);

        // printf("correct update after reassign:\n");
        // for(int i = 0; i < n; i++) printf("%d %d\n", i, szs.get(i));
        // printf("\n");
        time++;
    };

    auto get = [&](int i){
        pair<int, int> lead = szs.find(i);
        // printf("%d %d %d %d %d\n", time, i, lead.first, lead.second, a[rev[lead.first] + lead.second - 1] + 1);
        return a[rev[lead.first] + lead.second - 1] + 1;
    };

    reprocessrange(0, n);

    for(int i = 0; i < q;) {
        if(fixed) {
            qs[i].ans = get(qs[i].i);
            i++;
        } else {
            if(qs[i].t == time) {
                qs[i].ans = get(qs[i].i);
                i++;
            } else update();
        }
    }

    vector<int> ans(q); for(auto qx : qs) ans[qx.qi] = qx.ans;

    for(auto &i : ans) cout << i << '\n';
    
    return 0;
}

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