oj.uz

Submission #807583

# Submission time Handle Problem Language Result Execution time Memory
807583 2023-08-04T19:44:24 Z HaroldVemeno Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 27696 KB 
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int as[200000];

struct Node {
    int v;
    int s = 1;
    int p = rand();
    Node* l = nullptr;
    Node* r = nullptr;
    Node* c = nullptr;

    void print(ostream& o, string bef = string{}, int pos = 0) const {
        if(l == nullptr) {
            o << bef;
            if(pos == -1) o << "  ";
            if(pos == 1)  o << "| ";
            if(pos == 2)  o << "c ";
            o << ",-o\n";
        } else {
            if(pos == -1) l->print(o, bef + "  ", -1);
            if(pos == 1)  l->print(o, bef + "| ", -1);
            if(pos == 2) l->print(o, bef + "c ", -1);
            if(pos == 0)  l->print(o, bef, -1);
        }
        o << bef;
        if(pos == -1) o << ",-";
        if(pos == 1)  o << "`-";
        if(pos == 2)  o << "c-";
        o << "(v: " << v << ", p: " << p << ", s:" << s << ")\n";
        if(c) {
            if(pos == -1) c->print(o, bef + "| | ", 2);
            if(pos == 1) c->print(o, bef + "  | ", 2);
            if(pos == 2) c->print(o, bef + "  | ", 2);
            if(pos == 0) c->print(o, bef + "| ", 2);
        }
        if(r == nullptr) {
            o << bef;
            if(pos == -1) o << "| ";
            if(pos == 1)  o << "  ";
            if(pos == 2)  o << "  ";
            o << "`-o\n";
        } else {
            if(pos == -1) r->print(o, bef + "| ", 1);
            if(pos == 1)  r->print(o, bef + "  ", 1);
            if(pos == 2)  r->print(o, bef + "  ", 1);
            if(pos == 0)  r->print(o, bef, 1);
        }

    }

    friend ostream& operator<< (ostream& o, const Node* a) {
        o << '\n';
        if(!a) o << "o\n";
        else a->print(o);
        return o;
    }

};

Node buf[200000];

int size(Node* a) {
    return a?a->s:0;
}

void pull(Node* a) {
    if(a) {
        a->s = 1;
        a->s += size(a->l);
        a->s += size(a->r);
        a->s += size(a->c);
    }
}

Node* concat(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->p > b->p) {
        a->r = concat(a->r, b);
        pull(a);
        return a;
    } else {
        b->l = concat(a, b->l);
        pull(b);
        return b;
    }
}


pair<Node*, Node*> splitbyv(Node* a, int v) {
    if(!a) return {a, a};
    if(a->v < v) {
        auto [rl, rr] = splitbyv(a->r, v);
        a->r = rl;
        pull(a);
        return {a, rr};
    } else {
        auto [ll, lr] = splitbyv(a->l, v);
        a->l = lr;
        pull(a);
        return {ll, a};
    }
}

Node* merge2(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(b->p > a->p) swap(a, b);
    auto [l, r] = splitbyv(b, a->v);
    a->l = merge2(l, a->l);
    a->r = merge2(r, a->r);
    pull(a);
    return a;
}

Node* merge(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->s > b->s) swap(a, b);
    b = merge(a->l, b);
    a->l = nullptr;
    b = merge(a->r, b);
    a->r = nullptr;
    pull(a);
    auto [l, r] = splitbyv(b, a->v);
    b = concat(l, concat(a, r));
    return b;
}

struct SplitRes {
    Node* l;
    Node* m;
    Node* r;
};

SplitRes splitons(Node* a, int s) {
    D(s)
    D(a)
    if(!a) return {a, a, a};
    if( s <= size(a->l) ) {
        auto[l, m, r] = splitons(a->l, s);
        a->l = r;
        pull(a);
        return {l, m, a};
    } else if(s >= size(a->l) + size(a->c) + 1) {
        auto[l, m, r] = splitons(a->r, s - size(a->c) - size(a->l) - 1 );
        a->r = l;
        pull(a);
        return {a, m, r};
    } else {
        auto[l, m, r] = splitons(a->c, s - size(a->l) - 1);
        m = concat(m, r);
        a->c = l;
        auto ar = a->r;
        a->r = nullptr;
        pull(a);
        return {a, m, ar};
    }
}


int valuebys(Node* a, int s) {
    D(size(a))
    if(s < size(a->l)) {
        return valuebys(a->l, s);
    } else if(s == size(a->l)) {
        return a->v;
    } else if(s < size(a->l) + 1 + size(a->c)) {
        return valuebys(a->c, s - size(a->l) - 1);
    } else {
        return valuebys(a->r, s - size(a->l) - 1 - size(a->c));
    }
}

struct Q {
    int t;
    int ind;
    int i;
    int res;
};

void solve() {
    int n, q;
    cin >> n >> q;

    srand(4994040);

    vector<Q> qs(q);
    for(int i = 0; i < n; ++i) {
        cin >> as[i];
    }
    for(int i = 0; i < q; ++i) {
        cin >> qs[i].t >> qs[i].ind;
        --qs[i].ind;
        qs[i].i = i;
    }
    sort(all(qs), [](Q a, Q b){return a.t < b.t;});

    vector<Node*> trs;
    for(int i = n-1; i >= 0; --i) {
        Node* tr = buf+i;
        tr->v = as[i];
        tr->s = 1;
        tr->p = rand();
        while(!trs.empty() && trs.back()->v < tr->v) {
            tr->c = concat(tr->c, trs.back());
            trs.pop_back();
        }
        pull(tr);
        trs.push_back(tr);
    }
    Node* tr = nullptr;
    for(Node* t : trs) {
        tr = concat(t, tr);
    }
    trs.clear();
    D(tr);
    D(size(tr));

    int t = 0;
    bool changed = true;
    for(int i = 0; i < q; ++i) {
        D(i)
        while(changed && qs[i].t > t && t < 1000) {
            D(t)
            auto [l, m, r] = splitons(tr, n/2);
            if(m == nullptr) changed = false;
            D(l)
            D(m)
            D(r)
            l = merge(l, m);
            D(l)
            tr = concat(l, r);
            D(tr)
            ++t;
        }
        D(t)
        qs[i].res = valuebys(tr, qs[i].ind);
    }


    sort(all(qs), [](Q a, Q b){return a.i < b.i;});
    for(auto q : qs) cout << q.res << '\n';
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 27696 KB Output is correct
2 Correct 361 ms 27672 KB Output is correct
3 Correct 409 ms 26884 KB Output is correct
4 Correct 332 ms 26728 KB Output is correct
5 Correct 356 ms 27600 KB Output is correct
6 Correct 340 ms 26780 KB Output is correct
7 Correct 394 ms 27660 KB Output is correct
8 Correct 343 ms 26860 KB Output is correct
9 Correct 324 ms 26852 KB Output is correct
10 Correct 314 ms 27048 KB Output is correct
11 Correct 334 ms 26972 KB Output is correct
12 Correct 295 ms 26700 KB Output is correct
13 Correct 329 ms 27100 KB Output is correct
14 Correct 330 ms 27232 KB Output is correct
15 Correct 327 ms 27596 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 259 ms 27032 KB Output is correct
18 Correct 786 ms 26892 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 24584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 11768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 27696 KB Output is correct
2 Correct 361 ms 27672 KB Output is correct
3 Correct 409 ms 26884 KB Output is correct
4 Correct 332 ms 26728 KB Output is correct
5 Correct 356 ms 27600 KB Output is correct
6 Correct 340 ms 26780 KB Output is correct
7 Correct 394 ms 27660 KB Output is correct
8 Correct 343 ms 26860 KB Output is correct
9 Correct 324 ms 26852 KB Output is correct
10 Correct 314 ms 27048 KB Output is correct
11 Correct 334 ms 26972 KB Output is correct
12 Correct 295 ms 26700 KB Output is correct
13 Correct 329 ms 27100 KB Output is correct
14 Correct 330 ms 27232 KB Output is correct
15 Correct 327 ms 27596 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 259 ms 27032 KB Output is correct
18 Correct 786 ms 26892 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Execution timed out 3043 ms 24584 KB Time limit exceeded
22 Halted 0 ms 0 KB -