oj.uz

Submission #971364

# Submission time Handle Problem Language Result Execution time Memory
971364 2024-04-28T12:01:34 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 1626 ms 54808 KB 
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct nod {
    int sz, pmax, vmax, val;
    nod *l, *r;
} *nil = new nod{0, -1, -1, -1, 0, 0};

using ns = nod*;

vector<ns> ToDel;
ns nod_nou(int v) {
    ns re = new nod{1, 0, v, v, nil, nil};
    ToDel.push_back(re);
    return re;
}

ns mod_fiu(ns a, int side, ns f) {
    (side ? a->r : a->l) = f;
    a->sz = a->l->sz + a->r->sz + 1;
    int vl = a->l->vmax, eu = a->val, vr = a->r->vmax;
    if(vl > eu && vl > vr) {
        a->pmax = a->l->pmax;
        a->vmax = vl;
    }
    if(eu > vl && eu > vr) {
        a->pmax = a->l->sz;
        a->vmax = eu;
    }
    if(vr > vl && vr > eu) {
        a->pmax = a->r->pmax + a->l->sz + 1;
        a->vmax = vr;
    }
    return a;
}

mt19937 rng(1);

ns join(ns a, ns b) {
    return a == nil ? b :
        b == nil ? a :
        uniform_int_distribution<int>(1, a->sz + b->sz)(rng) <= a->sz ? 
            mod_fiu(a, 1, join(a->r, b)) /// a este tata
            : mod_fiu(b, 0, join(a, b->l));
}

struct pns {
    ns l, r;
};

pns split(ns a, int cnt) {
    if(cnt > a->sz) {
        cout << "Split prost\n";
        exit(0);
    }
    if(a == nil)
        assert(!a->sz);
    pns tmp;
    return !cnt ? pns{nil, a} :
            cnt == a->sz ? pns{a, nil} : 
            a->l->sz >= cnt ? 
                (tmp = split(a->l, cnt), tmp.r = mod_fiu(a, 0, tmp.r), tmp)
             : (tmp = split(a->r, cnt - a->l->sz - 1), tmp.l = mod_fiu(a, 1, tmp.l), tmp);
}

void afis(ns a) {
    if(a == nil) return;
    afis(a->l);
    cout << a->val + 1 << " ";
    afis(a->r);
}

vector<ns> Sparge(ns a) {
    vector<ns> Re;
    while(a->pmax) {
        pns doi = split(a, a->pmax);
        Re.push_back(doi.r);
        a = doi.l;
    }
    Re.push_back(a);
    return Re;
}

struct AIB {
    int n;
    vi V;

    AIB(int N) : n(N + 1), V(N + 1, 0) {}
    
    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] += v;
            p += p & -p;
        }
    }

    int cauta(int v) {
        ///vreau prima pozitie pt care query(p) >= v 
        int p = 0;
        for(int step = 20; step >= 0; --step)
            if(p + (1 << step) < n && v >= V[p + (1 << step)]) {
                p += (1 << step);
                v -= V[p];
            }
        return p;
    }

    int query(int p) {
        ++p;
        int re = 0;
        while(p) {
            re += V[p];
            p -= p & -p;
        }
        return re;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    
    vi V0(n, 0);
    ns A = nil, B = nil;
    for(int i = 0; i < n; ++i) {
        cin >> V0[i];
        --V0[i];
        if(i < n / 2) A = join(A, nod_nou(V0[i]));
        else B = join(B, nod_nou(V0[i]));
    }
    AIB Sume(n);

    auto SA = Sparge(A), SB = Sparge(B);
    vector<ns> V(n, nil);
    vi Sz(n, 0);

    auto update = [&](ns nod, int sgn) {
        if(nod == nil) return;
        Sz[nod->vmax] += sgn * nod->sz;
        V[nod->vmax] = nod;
        Sume.update(nod->vmax, sgn * nod->sz);
    };

    vector<vector<ii> > Q(n + 2);
    vi Re(q, 0);
    for(int i = 0; i < q; ++i) {
        int t, p;
        cin >> t >> p;
        Q[min(t, n)].push_back({i, p});
    }
    for(auto [id, p] : Q[0]) Re[id] = V0[p - 1];

    for(auto it : SA) 
        update(it, 1);
    for(auto it : SB) 
        update(it, 1);

    for(int t = 1; t <= n; ++t) {
        for(auto [id, p] : Q[t]) {
            int p1 = Sume.cauta(p - 1);
            ns eu = V[p1];
            int nr = p - Sume.query(p1 - 1) - 1;
            pns a = split(eu, nr);
            pns b = split(a.r, 1);
            Re[id] = b.l->val;
            eu = join(a.l, join(b.l, b.r));
            V[p1] = eu;
        }
        int p = Sume.cauta(n / 2);
        if(Sume.query(p) == n / 2) { /// nu trebuie facut nimic
            continue;
        }
        update(V[p], -1);
        pns nou = split(V[p], n / 2 - Sume.query(p - 1));
        update(nou.l, 1);
        update(nou.r, 1);
    }

    for(auto it : Re)
        cout << it + 1 << "\n";

    for(auto it : ToDel)
        delete it;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 18512 KB Output is correct
2 Correct 532 ms 24920 KB Output is correct
3 Correct 529 ms 24088 KB Output is correct
4 Correct 961 ms 22792 KB Output is correct
5 Correct 918 ms 26616 KB Output is correct
6 Correct 954 ms 25848 KB Output is correct
7 Incorrect 920 ms 27112 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 38224 KB Output is correct
2 Correct 744 ms 54808 KB Output is correct
3 Correct 772 ms 48148 KB Output is correct
4 Correct 1264 ms 44856 KB Output is correct
5 Correct 1234 ms 46964 KB Output is correct
6 Correct 1323 ms 44332 KB Output is correct
7 Incorrect 1626 ms 51616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 13208 KB Output is correct
2 Correct 140 ms 15044 KB Output is correct
3 Correct 158 ms 14528 KB Output is correct
4 Correct 251 ms 13836 KB Output is correct
5 Correct 236 ms 14416 KB Output is correct
6 Correct 232 ms 13724 KB Output is correct
7 Incorrect 238 ms 14356 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 18512 KB Output is correct
2 Correct 532 ms 24920 KB Output is correct
3 Correct 529 ms 24088 KB Output is correct
4 Correct 961 ms 22792 KB Output is correct
5 Correct 918 ms 26616 KB Output is correct
6 Correct 954 ms 25848 KB Output is correct
7 Incorrect 920 ms 27112 KB Output isn't correct
8 Halted 0 ms 0 KB -