제출 #1356502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356502		AMel0n	Abracadabra (CEOI22_abracadabra)	C++20	10 / 100	3094 ms	28068 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define last(v) prev((v).end())

int N, Q;
vector<int> A;
struct block {
    int v, l, r, len;
    block(int vv, int ll, int rr) {v = vv, l = ll, r = rr, len = r-l+1;}
    bool operator<(const block &other) const {
        return v < other.v;
    }
};
set<block> deck, del;
vector<int> nxt;

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> Q;
    A.resize(N), nxt.resize(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    vector<vector<pair<int,int>>> ask(N+1);
    vector<int> res(Q);
    for(int i = 0; i < Q; i++) {
        int t, p;
        cin >> t >> p; p--;
        ask[min(N, t)].push_back({p, i});
    }

    vector<int> stk = {N};
    for(int i = N-1; i >= 0; i--) {
        while(stk.size() > 1 && A[stk.back()] < A[i]) stk.pop_back();
        nxt[i] = stk.back();
        stk.push_back(i);
    }

    int cur = 0;
    while(cur < N) {
        deck.insert({A[cur], cur, nxt[cur]-1});
        cur = nxt[cur];
    }

    auto query = [&] (int q) {
        for(auto it = deck.begin(); it != deck.end(); it++) {
            if (q - it->len >= 0) q -= it->len;
            else {
                return A[it->l + q];
            }
        }
        for(auto it = del.begin(); it != del.end(); it++) {
            if (q - it->len >= 0) q -= it->len;
            else {
                return A[it->l + q];
            }
        }
    };

    int sz = N;
    for(int t = 0; t <= N; t++) {
        for(auto &[q, qi]: ask[t]) {
            res[qi] = query(q);
        }

        while(sz - last(deck)->len >= N/2) sz -= last(deck)->len, del.insert(*last(deck)), deck.erase(last(deck));

        block split = *last(deck);
        deck.erase(last(deck));
        deck.insert({split.v, split.l, split.r - (sz - N/2)});

        int cur = split.r - (sz - N/2) + 1;
        while(cur <= split.r) {
            deck.insert({A[cur], cur, min(split.r, nxt[cur]-1)});
            cur = nxt[cur];
        }
    }

    for(int i = 0; i < Q; i++) cout << res[i] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In lambda function:
Main.cpp:57:5: warning: control reaches end of non-void function [-Wreturn-type]
   57 |     };
      |     ^

• 서브태스크 1: 10 / 10
• 서브태스크 2: 0 / 40
• 서브태스크 3: 0 / 25
• 서브태스크 4: 0 / 25