Submission #1226283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226283		slivajan	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	420 ms	29632 KiB

Main

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

using un = long long;
using vuc = vector<un>;
using vol = vector<bool>;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

un N;
vuc vel;
vuc zac;

vuc A;

vuc vel_iv;
un M;
void init_iv(){
    M = vel.size();
    while(M&(M-1)) M++;

    REP(i, 0, vel.size()) vel_iv[i+M] = vel[i];

    for (un i = M-1; i > 0; i--){
        vel_iv[i] = vel_iv[2*i] + vel_iv[2*i + 1];
    }
}

un get_iv(un i) {return vel_iv[M+i];} 
un set_iv(un i, un v){
    i += M;
    vel_iv[i] = v;

    i/= 2;
    while(i > 0) vel_iv[i] = vel_iv[2*i] + vel_iv[2*i + 1];
}

pair<un, un> dostat_pozicy(un i){
    un ptr = 1;
    while(ptr < M){
        if (vel_iv[2*ptr] <= i) {
            ptr = 2*ptr;
        }
        else{
            i -= vel_iv[2*ptr];
            ptr = 2*ptr + 1;
        }
    }

    return {ptr-M, i-1};

}

un dostat(un i){
    auto [a, b] = dostat_pozicy(i);
    return A[zac[a] + b];
}

bool doStep(){
    auto [a, b] = dostat_pozicy(N/2);

    if (b == 0) return true;

    un nej = -1;
    REP(i, zac[a]+b, zac[a]+get_iv(a)){
        if (A[i] > nej){
            if (nej != -1) set_iv(nej, vel[nej]);
            nej = A[i];
        } 
        vel[nej]++;
    }

    set_iv(a, b);

    return false;
}

int main(){
    un Q; cin >> N >> Q;

    A = vuc(N); FEAC(a, A) cin >> a;
    FEAC(a, A) a--;

    vel = vuc(N, 0);
    zac = vuc(N, -1);

    vec<tuple<un, un, un>> queries;
    REP(i, 0, Q){
        un a, b; cin >> a >> b;
        b--;
        queries.emplace_back(a, b, i);
    }

    sort(ALL(queries));

    un nej = -1;
    REP(i, 0, N){
        zac[A[i]] = i;
        if (A[i] > nej) nej = A[i];
        vel[nej]++;
    }

    init_iv();

    vuc rets(Q, -1);
    un qIndex = 0;

    un t = 0;

    while(qIndex < Q){
        while((qIndex < Q) and (get<0>(queries[qIndex]) == t)){
            auto [ignore, i, j] = queries[qIndex];
            rets[j] = dostat(i);
            qIndex++;
        }

        bool hotovo = doStep();
        t++;

        if (hotovo) break;
    }

    while(qIndex < Q){
        auto [ignore, i, j] = queries[qIndex];
        rets[j] = dostat(i);
        qIndex++;
    }



    FEAC(ret, rets) cout << ret+1 << endl;

}

Compilation message (stderr)

Main.cpp: In function 'un set_iv(un, un)':
Main.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
   39 | }
      | ^

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